Runtime error: Process terminated with status 255

[carleye]

I am trying to find the 10001st prime number. It shows runtime error.

#include<iostream>
using namespace std;
void pnum(int n)
{
long long int i,j,a[n],cnt=0;
for(i=3;i<9000000000;i++)
{
    for(j=2;j<i;j++)
    {
        if(i%j==0)
        break;
        else
         {
            if(j==i-1)
            {
                a[cnt]=i;
                cnt=cnt+1;
            }
            else
                continue;
         }
    }
}
cout<<a[n-2]<<"\n";   /*a[n-2] as i have skipped the first prime number i.e. 2 so a[2] will actually be 4th prime number*/
}
int main()
{
    pnum(10001);
return 0;
}

[TheIdeasMan]

Hi,

First of all please always use code tags: http://www.cplusplus.com/articles/z13hAqkS/

It seems that particular error has nothing to do with the code:

https://stackoverflow.com/questions/25102799/process-terminated-with-status-255

Btw, I found this with a net search - something you should have done before asking a question. That is, unless you live in Nth Korea or Iran or somewhere with internet restrictions.

Your algorithm is very inefficient, if you try it with big numbers it will be terribly slow. Have a look on the wiki page, you will find better algorithms. Another is https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Euler.27s_Sieve.

This is a question from Project Euler, the big thing to learn there is that brute force methods are not the way to go. One has to come up with a clever method of arriving at the answer. So it involves some research: wiki and Google are you best friends there.

Another thing is the use of break and continue, they only work for the inner most loop.

Instead of a for loop with a large value for the limit, consider a while loop with 10,001 as the limit. for loops are good when you know exactly how many times to loop.

Good Luck !!

[JLBorges]

1. Use the prime number theorem to get an upper bound on the 10,001^st prime number.
https://en.wikipedia.org/wiki/Prime_number_theorem#Approximations_for_the_nth_prime_number

2. Generate a prime number sieve for numbers up to the upper bound calculated in step 1.

#include <iostream>
#include <cmath>

int main()
{
   const std::size_t N = 10'001 ; // we are interested in the 10,001st prime number

   // use the prime number theorem to get an upper bound on the nth prime
   // http://en.wikipedia.org/wiki/Prime_number_theorem
   const auto logn = std::log(N) ;
   const std::size_t ubound = N * ( logn + std::log(logn) ) + 1 ;

   std::cout << "the " << N << "th prime number is less than " << ubound << '\n' ;

   // generate a prime number sieve for numbers up to ubound
   // http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
   // print out the Nth prime number
} 

[carleye]

I tried it with Seive but no luck. I an getting a runtime error, i guess it is because of the long int. I looked in stackoverflow, it tells to change the console in c::b but i can't change it though.

#include<iostream>
#include<cstring>
using namespace std;
void pnum(long int n)
{  long int i,j,cnt=0,a[10000];

    bool seive[n+1];
    memset(seive,true,sizeof(seive));
    for(i=2;i*i<=n;i++)
    {
        if(seive[i]==true)
        {
            for(j=2*i;j<=n;j=j+i)
            {
                seive[j]=false;
            }
        }
    }
    for(i=2;i<=n;i++)
    {
        if(seive[i])
        {   a[cnt+1]=i;
        cnt++;
        }
    }
    cout<<a[60];
}

int main()
{
    pnum(200000);
return 0;
}

[JLBorges]

#include <iostream>
#include <cmath>
#include <vector>

int main()
{
   const std::size_t N = 10'001 ; // we are interested in the 10,001st prime number

   // use the prime number theorem to get an upper bound on the nth prime
   // http://en.wikipedia.org/wiki/Prime_number_theorem
   const auto logn = std::log(N) ;
   const std::size_t ubound = N * ( logn + std::log(logn) ) + 1 ;

   std::cout << "the " << N << "th prime number is less than " << ubound << '\n' ;

   // generate a prime number sieve for numbers up to ubound
   // http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
   std::vector<int> sieve( ubound, true ) ;
   const std::size_t ub_root = std::sqrt(ubound) + 2 ;
   for( std::size_t i = 2 ; i < ub_root ; ++i ) if( sieve[i] )
       for( std::size_t j = i+i ; j < ubound ; j += i ) sieve[j] = false ;

   // print out the Nth prime number
   std::size_t cnt = 0 ;
   std::size_t i = 2 ;
   for( ; cnt < N ; ++i ) if( sieve[i] ) ++cnt ;
   std::cout << "the " << N << "th prime number is " << i-1 << '\n' ;
} 

http://coliru.stacked-crooked.com/a/8773a7ce75116793

[ne555]

@carleye: `a' is too small in your last code.
n = 200e3
n/ln(n) ~ 16.4e3
but `a' has only a size of 10e3.
so out of bounds access .


By the way, in my case when `cnt' was 10007, line 22 overwrites it to about 104e3 and that made gdb and valgrind jump in the next iteration.
¿is there a way to make them detect the invalids writes when cnt is in the [10000; 10006] range? I mean, access outside of the declared array size, altought perhaps is still inside the stack.
edit: http://valgrind.org/docs/manual/sg-manual.html
edit2: -fsanitize=undefined and -fsanitize=address, sadly the `address' options aborts the program, so can't analyse it under gdb.

[carleye]

@ne555 yeah! it was because of array size being too small.