алгоритм — C ++ — Сито Аткина, возвращающее несколько композитов
Я сделал свою собственную реализацию Sieve of Atkin в C ++, она генерирует простые числа примерно до 860 000 000. Где-то там и выше программа начинает возвращать несколько композитов, или я так думаю. У меня внутри программы есть переменная, которая считает количество найденных простых чисел, и при ~ 860 000 000 это число больше, чем должно быть. Я проверил мой счет по аналогичной программе для Сита Эратосфена и нескольким интернет-ресурсам. Я новичок в программировании, так что это, вероятно, глупая ошибка.
Во всяком случае, вот оно:
#include <iostream>
#include <math.h>
#include <time.h>
int main(int argc, const char * argv[])
{
long double limit;
unsigned long long int term,term2,x,y,multiple,count=2;
printf("Limit: ");
scanf("%Lf",&limit);
int root=sqrt(limit);
int *numbers=(int*)calloc(limit+1, sizeof(int));
clock_t time;//Starts Stopwatch
time=clock();for (x=1; x<root; x++) {
for (y=1; y<root; y++) {
term2=4*x*x+y*y;
if ((term2<=limit) && (term2%12==1 || term2%12==5)){
numbers[term2]=!numbers[term2];
}
term2=3*x*x+y*y;
if ((term2<=limit) && (term2%12==7)) {
numbers[term2]=!numbers[term2];
}
term2=3*x*x-y*y;
if ((term2<=limit) && (x>y) && (term2%12==11)) {
numbers[term2]=!numbers[term2];
}
}
}//Print 2,3
printf("2 3 ");//Sieves Non-Primes That Managed to Get Through
for (term=5; term<=root; term++) {
if (numbers[term]==true) {
multiple=1;
while (term*term*multiple<limit){
numbers[term*term*multiple]=false;
multiple++;
}
}
}
time=clock()-time;
for (term=5; term<limit; term++) {
if (numbers[term]==true) {
printf("%llu ",term);
count++;
}
}printf("\nFound %llu Primes Between 1 & %Lf in %lu Nanoseconds\n",count,limit,time);return 0;
}
Решение
От википедия ,
The following is pseudocode for a straightforward version of the algorithm:
// arbitrary search limit
limit ← 1000000
// initialize the sieve
for i in [5, limit]: is_prime(i) ← false
// put in candidate primes:
// integers which have an odd number of
// representations by certain quadratic forms
for (x, y) in [1, √limit] × [1, √limit]:
n ← 4x²+y²
if (n ≤ limit) and (n mod 12 = 1 or n mod 12 = 5):
is_prime(n) ← ¬is_prime(n)
n ← 3x²+y²
if (n ≤ limit) and (n mod 12 = 7):
is_prime(n) ← ¬is_prime(n)
n ← 3x²-y²
if (x > y) and (n ≤ limit) and (n mod 12 = 11):
is_prime(n) ← ¬is_prime(n)
// eliminate composites by sieving
for n in [5, √limit]:
if is_prime(n):
// n is prime, omit multiples of its square; this is
// sufficient because composites which managed to get
// on the list cannot be square-free
for k in {n², 2n², 3n², ..., limit}:
is_prime(k) ← false
print 2, 3
for n in [5, limit]:
if is_prime(n): print n
для (x, y) в [1, √limit] × [1, √limit]: это твоя проблема.
Вы использовали:
for (x=1; x<root; x++)
for (y=1; y<root; y++)
Вместо этого используйте:
for (x=1; x<=root; x++)
for (y=1; y<=root; y++)
Надеюсь это поможет !
Другие решения
Других решений пока нет …