Массив простых чисел на С

Для поиска простых чисел используйте алгоритм Решето Эратосфена. Не смотрите на эти странные примеры.

Вот тут есть код.

Arrays.fill(isPrime,true);
isPrime[1] = false;
for (int i=2; i*i < N; i++)
   if (isPrime[i])
      for (int j=i*i; j < N; j+=i)
         isPrime[j] = false;

Ошибся немного - там на яве. Но смысл тот же

int limit = 1000;
int sqr_lim;
bool is_prime[1001];
int x2, y2;
int i, j;
int n;

// Инициализация решета
sqr_lim = (int)sqrt((long double)limit);
for (i = 0; i <= limit; i++) is_prime[i] = false;
is_prime[2] = true;
is_prime[3] = true;

// Предположительно простые - это целые с нечетным числом
// представлений в данных квадратных формах.
// x2 и y2 - это квадраты i и j (оптимизация).
x2 = 0;
for (i = 1; i <= sqr_lim; i++) {
    x2 += 2 * i - 1;
    y2 = 0;
    for (j = 1; j <= sqr_lim; j++) {
        y2 += 2 * j - 1;

        n = 4 * x2 + y2;
        if ((n <= limit) && (n % 12 == 1 || n % 12 == 5))
            is_prime[n] = !is_prime[n];

        // n = 3 * x2 + y2; 
        n -= x2; // Оптимизация
        if ((n <= limit) && (n % 12 == 7))
            is_prime[n] = !is_prime[n];

        // n = 3 * x2 - y2;
        n -= 2 * y2; // Оптимизация
        if ((i > j) && (n <= limit) && (n % 12 == 11))
            is_prime[n] = !is_prime[n];
    }
}

// Отсеиваем кратные квадратам простых чисел в интервале [5, sqrt(limit)].
// (основной этап не может их отсеять)
for (i = 5; i <= sqr_lim; i++) {
    if (is_prime[i]) {
        n = i * i;
        for (j = n; j <= limit; j += n) {
            is_prime[j] = false;
        }
    }
}

// Вывод списка простых чисел в консоль.
printf("2, 3, 5"); 
for (i = 6; i <= limit; i++) {  // добавлена проверка делимости на 3 и 5. В оригинальной версии алгоритма потребности в ней нет.
    if ((is_prime[i]) && (i % 3 != 0) && (i % 5 !=  0)){
       printf(", %d", i);
    }
}

Это один из алгоритмов нахождения простых чисел "Решето Аткина"

Допустим, что речь идет о первых N простых числах. Поместим в массив P[N] первые 3 {1, 2, 3}. Вспомним, что простое число нечетное, поэтому будем перебирать только нечетные. Если очередной кандидат окажется простым, добавим его в массив и увеличим M - текущее количество простых в массиве (в начале установим M=3).

Очевидно, что испытывать надо числа, начиная с P[M-1]+2 (назовем его K). В качестве делителя будем брать уже найденные простые числа, начиная с P[2] (т.е. тройки). Если квадрат очередного делителя (P[i]*P[i]) больше K, то K простое число, занесем его в P, если выяснили, что K составное, то увеличим его на 2.

Повторяем, пока не наберем N простых чисел.

Для достаточно больших чисел возведение в квадрат вызовет переполнение, этот момент надо отследить и учесть при определении условия прекращения цикла выбора делителей. Эффективное решение в голову, что-то не приходит, понятно, что это K, деленное на что-то (в таком случае будут лишние испытания кандидата).

void fill_primes(int* arr, size_t siz)
{
    int prime = 2;
    while( siz-- ) {
        *arr++ = prime;
        prime = 5 - prime;
    }
}