Помогите найти ошибку в алгоритме. Он пропускает число 4 как простое

204
11 октября 2017, 08:30
#include <iostream>
#include <vector>
using  namespace std;
bool is_prime(unsigned int num){ 
int limit = num;
int sqr_lim;
vector<bool> is_prime_f(num + 10);
int x2, y2;
int i, j;
int n;
// Инициализация решета
sqr_lim = (int)sqrt((long double)limit);
for (i = 0; i <= limit; i++) is_prime_f[i] = false;
is_prime_f[2] = true;
is_prime_f[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_f[n] = !is_prime_f[n];
        // n = 3 * x2 + y2; 
        n -= x2; // Оптимизация
        if ((n <= limit) && (n % 12 == 7))
            is_prime_f[n] = !is_prime_f[n];
        // n = 3 * x2 - y2;
        n -= 2 * y2; // Оптимизация
        if ((i > j) && (n <= limit) && (n % 12 == 11))
            is_prime_f[n] = !is_prime_f[n];
    }
}
// Отсеиваем кратные квадратам простых чисел в интервале [5, sqrt(limit)].
// (основной этап не может их отсеять)
for (i = 5; i <= sqr_lim; i++) {
    if (is_prime_f[i]) {
        n = i * i;
        for (j = n; j <= limit; j += n) {
            is_prime_f[j] = false;
        }
    }
}
// Вывод списка простых чисел в консоль.
//printf("2, 3, 5");
if ((i == 2) || (i == 3) || (i == 5))
    return true;
for (i = 6; i <= limit; i++) {  // добавлена проверка делимости на 3 и 5. В оригинальной версии алгоритма потребности в ней нет.
    if ((is_prime_f[i]) && (i % 3 != 0) && (i % 5 !=  0)){
       //printf(", %d", i);
             if (i == num)
                 return true;
    }
}
    return 0; 
}
int main(int argc, char* argv[]){
    if (is_prime(983)){
        cout << "prime" << endl;
    }   else {
        cout << "not prime" << endl;
    }
    return 0;
}
READ ALSO
Реализация алгоритма Хеш-функция [требует правки]

Реализация алгоритма Хеш-функция [требует правки]

Помогите пожалуйста создать алгоритм реализации хеш-функции и реализовать его на С++

146
Драйвер для HDD [требует правки]

Драйвер для HDD [требует правки]

Собственно то, что я сейчас понимаю: Необходимо написать драйвер для HDD (Для устройства, а не файловой системе), тк

214
Исключения из перебора бит по шаблону

Исключения из перебора бит по шаблону

Вдохновленный этим вопросом Bit hack to generate all integers with a given number of 1s интересует, а возможно ли пропускать в генерации значений содержащих определенный...

186
Как закрыть клиентское соединение в libevent?

Как закрыть клиентское соединение в libevent?

Как закрыть клиентское соединение средствами библиотеки libevent (на с++) после получения ответа от сервера, чтобы файловый дескриптор используемый...

288