алгоритм — Сито Atkin C ++ Реализация не помечает некоторые простые числа

Я реализовал Sieve of Atkin в C ++ для возврата вектора типа bool, но он не помечает некоторые простые числа.

// Example program
#include <iostream>
#include <vector>

std::vector<bool> listPrimes(int limit){
std::vector<bool> primes(limit);

primes[2] = primes[3] = true;

for(int i=1; i*i < limit; ++i){
for(int j=1; j*j < limit; ++j){

int n = (4*i*i) + (j*j);
if (n <= limit && (n % 12 == 0 || n % 12 == 5 ))
primes[n] = !primes[n];

n = (3*i*i) + (j*j);
if (n <= limit && n % 12 == 7 )
primes[n] = !primes[n];

n = (3*i*i) - (j*j);
if ( i > j && n <= limit && n % 12 == 11 )
primes[n] = !primes[n];
}
}

for(int i=5; i*i < limit; ++i ){
if(primes[i])
for(int j=i*i; j < limit; j+=i*i)
primes[i] = false;
}

return primes;
}

int main()
{
std::vector<bool> primes = listPrimes(100);

for(int i=0; i < 100; ++i)
if(primes[i])
std::cout << i << ", ";

return 0;
}

Вот вывод данного кода.
2, 3, 11, 17, 19, 23, 29, 31, 41, 43, 47, 53, 59, 67, 71, 72, 79, 83, 89,

Что я делаю неправильно ?

0

Решение

Задача ещё не решена.

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]