Я застрял с этой проблемой на spoj.com
http://www.spoj.com/problems/PRIME1/
Прочитав немного об алгоритмах простого поколения, я обнаружил, что «Сито Аткинса» является самым быстрым алгоритмом простого поколения. Я частично реализовал алгоритм с помощью этого урока http://www.geeksforgeeks.org/sieve-of-atkin/
Когда я запустил код, это дало мне ошибку сегментации. После отладки я узнал, что этот код не оптимален, он использует больше памяти, памяти. Может кто-нибудь сказать мне, как я могу оптимизировать программу. Вот мой фрагмент кода. И да, это неполно.
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int sieveOfAtkin(long int limit)
{
// if limit is either 2 or 3, print them
if (limit >= 2)
{
cout << 2 << endl;
}
if (limit >= 3)
{
cout << 3 << endl;
}bool sieve[limit];
for (long int i=0; i<=limit; i++)
sieve[i] = false;
for (long int x=1; x<limit; x++)
{
for (long int y=1; y<limit; y++)
{
long int n = (4*x*x) + (y*y);
if (n<=limit && (n%12==1 || n%12==5))
sieve[n] ^= true;
n = (3*x*x) + (y*y);
if (n<=limit && (n%12==7))
sieve[n] ^= true;
n = (3*x*x) - (y*y);
if (x>y && n<=limit && (n%12==11))
sieve[n] ^= true;
}
}
for (long int r=5; r*r<limit; r++)
{
if(sieve[r])
{
for(long int i=r*r; i<limit; i+=r*r)
sieve[r] = false;
}
}
for (long int i=5; i<limit; i++)
if(sieve[i])
cout << i << endl;
return 0;
}
int main(void)
{
long int x;
cin >> x;
sieveOfAtkin(x);
return 0;
}
Во-первых, это интернет-миф, что Сито Аткина быстрее, чем Сито Эратосфена. Сито Аткина быстрее при определенных ограничениях, но Сито Эратосфена в целом быстрее и является ситом, выбранным математиками, которые фактически используют его для исследования простых чисел.
Во-вторых, когда сито становится слишком большим, чтобы поместиться в памяти, вы можете сегмент сито Увидеть этот ответ для деталей.
Других решений пока нет …