Я пытался решить этот вопрос на SPOJ.
http://www.spoj.com/problems/PRIME1/
Я получаю SIGABRT или SIGKILL. Что не так? Это работает нормально на моем компиляторе (CodeBlocks).
Я использую стандартный алгоритм Sieve of Erastosthenes.
//finding if a number is prime or not
bool is_Prime(int num)
{
if ( num <= 1)
return false;
int upper_limit = sqrt(num);
for( int i = 2; i <= upper_limit ; ++i)
if( num % i == 0)
return false;
return true;
}
bool is_prime_array [ 1000000000 ];
void sieve_of_erastosthenes( int MAX )
{
is_prime_array[1] = false;
for(int i=2; i <= MAX ; ++i )
is_prime_array[i]=true;
int upper_limit = sqrt(MAX);
for(int i = 2 ; i <= upper_limit ; ++i)
if ( is_Prime(i) )
for ( int j = i*i ; j<=MAX ; j += i)
is_prime_array[j]= false;
}
int main()
{int T, left, right;
cin.sync_with_stdio(false);
cin>>T;
while ( T-- )
{
cin >> left >> right;
sieve_of_erastosthenes( right );
for(int i = left ; i <= right ; ++i )
if(is_prime_array[i] == true )
cout<<i<<endl;
}
return 0;
}
Возможно, потому что ваш is_prime_array занимает 1 ГБ памяти.
И, кроме того, это не сито Эратосфена.
Других решений пока нет …