find the nth prime prime number

[cse.avinash]

Hello every one
Can I have a better algorithm to find the nth prime number, where 1<= n <=5000000.

for e.g.,
1st prime number is 2.
10th prime number is 29.
100th prime number is 541.
1000th prime number is 7919.
10000th prime number is 104729.
100000th prime number is 1299709.
1000000th prime number is 15485863.

Here is my code:--

#include<stdio.h>
#include<math.h>
long long arr[100000000]={0};
long long arr1[100000000];
int main() {
    long long i,j,num,inc=2,m=0,root,q,k;
    start=clock();
    num=86028130;    
    root=sqrt(num)+1;
    for(i=0;i<num;i++)arr[i]=i;
    for(i=2;i<=root;i++){
       if(arr[i]>0) {
          for(j=inc*i;j<=num;j=j+i)
            arr[j]=-1;
           inc++;
      }
    }
    for(i=0;i<num;i++) if(arr[i]>1) arr1[m++]=i;
    printf("Enter value of q-");
    scanf("%lld",&q);
    while(q--){
               printf("enter the nth prime number to be found:--");
               scanf("%lld",&k);
               printf("%lld\n",arr1[k-1]);
    }
          return 0;
}

range for q is <= 50000 and k inclusive 1 and 5000000.
time limit for this problem must be 10s.

but time limit for my program is exceeding for q=10.
help me with more efficient algo or techniques.

[WaltP]

Skip all even numbers. That will cut your loop in half: for(i=3;i<=root;i+=2)

[cse.avinash]

@WaltP:- Thanks for replying but its not working as its not printing the correct prime numbers less than 50.

check the code:--

#include<stdio.h>
#include<math.h>
long long arr[100000000]={0};
long long arr1[100000000];
int main() {
    long long i,j,num,inc=2,m=0,root,q,k;
    num=50;    
    root=sqrt(num)+1;
    for(i=0;i<num;i++)arr[i]=i;
    for(i=3;i<=root;i=i+2) //edited part as told by WaltP
    { 
       if(arr[i]>0) {
          for(j=inc*i;j<=num;j=j+i)
            arr[j]=-1;
           inc++;
      }
    }
    for(i=0;i<num;i++) if(arr[i]>1) arr1[m++]=i;
    for(i=0;i<m;i++)fprintf(stdout,"%lld,",arr1[i]);
    return 0;
}

[Adak]

You need the program to find up to 1 million prime numbers, in 5 seconds?

That's a job for ya! ;)

I just tried out my trusty prime number finder, and it took it 5.8 seconds with a pretty fast i7 cpu system (3.5GHz).

To go from 10 seconds to 5, you are right to look at your algorithm. And yours looks sophisticated, but completely foreign to me. What do you call that algorithm?

And when you say your program takes 10 seconds to run, what is the type of cpu and the speed it's running at?

We need some details! ;)

[cse.avinash]

I am not saying my program runs at 10 seconds.
I am mentioning only that the time limit for the probelem should be at most 10 seconds , but my code is taking much more time ,so i need some guidance in this regard to improve the time complexity.

[Adak]

And up to the 5 millionth prime number, in just 10 seconds?

On what kind of PC?

They have more efficient algorithms for this, but I can improve my "old reliable" program by using the idea that every non-prime number is divisible by a lesser prime number. So all the numbers being tested don't need to be tested against every odd number. Only the primes already found (if you're working up from 2), which are <= the sqr root of the number.

I might be able to make that time on my PC, with that improvement, but I'd never get that to run in 10 seconds, on an older system. For that, you'd need a better algorithm.

[cse.avinash]

I am using core 2 duo porcessor.

I got this question from this site,

I am trying to solve this question from a week now my heads are stuck off with this question and I want to do it.
I saw that 300 users have solved this question i.e., its not an impossible work.(Click on the best solutions in the link which i gave ).
what i need is just to improve my algo or think more on it.

[Smeagel13]

Are you allowed to stick some sneaky bits in?

e.g. if the input is 1000 you start from 7919 and skip everything below 7919 ...

[cse.avinash]

@Smeage:-- I didn't get your words. please explain more .

and 1000th prime number is 7917 i.e., when user enters 1000 output should be 7917.

[Adak]

If we're OK to just report the number, and not calculate it, then you could put the primes all up into an array, and simply return:

printf("%lu", AllPrimes[kthPrime]);

There are special ways to calculate the kth prime number, but when you see best times of 0.54 seconds, for numerous kth primes (many quite large), then I believe they aren't calculating those primes - they're initializing an array of primes, for quick access.

I tweaked my trial division prime number program, down from 67 seconds, to 19.6 seconds, for finding all primes up to the 5,000,000th prime. That's using all the tricks I know, so I'm calling trial division definitely the wrong way to meet this challenge. :(

But there are faster ways to find prime numbers than trial division. ;)

More after I chat with my muse. (Google a bit)

[Smeagel13]

@Smeage:-- I didn't get your words. please explain more .

and 1000th prime number is 7917 i.e., when user enters 1000 output should be 7917.

It's kind of a mix between what Adak said and actually calculating them, if the input is to find the 1500th prime number then, you know it won't be 7917 or less ... so start the test number at 7917 and you've avoided testing ~4k numbers!

Just like there is no point in starting the test number at 1 because we know that's a prime number ... and then we skip all the even numbers, just finding ways to avoid unnecessary processing.

[Adak]

So following the Smeagel plan, we'd need the list of primes, but I believe we could space them about 1,000 prime numbers apart. For 100,000 example, the file we'd need would be this: (not checked for accuracy, btw).
7919 << the 1,000 prime
17389 << the 2,000 prime
27449 etc.
37813
48611
59359
70657
81799
93179
104729
116447
128189
139901
151703
163841
176081
187963
200183
212369
224737
237203
249439
262139
274529
287117
300023
312583
324949
337541
350377
363269
376127
389171
401987
414977
427991
440723
453889
467213
479909
493127
506131
519227
532333
545747
559081
572311
585493
598687
611953
625187
638977
652429
665659
679277
692543
706019
719639
732923
746773
760267
773603
787207
800573
814279
827719
841459
855359
868771
882377
896009
909683
923591
937379
951161
965113
978947
993107
1006721
1020379
1034221
1048129
1062511
1076143
1090373
1103923
1117579
1131617
1145689
1159523
1173301
1187003
1200949
1215133
1229269
1243709
1257517
1271293
1285517
1299709

but you wouldn't have this in a file, you'd assign those values in an array of numbers you declared in your program, able to hold up to 5,000 numbers, for this example.

To be under 10 seconds in total time, if you have 8 searches to conduct, you can only use 1.19 seconds maximum, per search - and that's cutting it VERY close.

So, do you want to start a program to meet the contest challenge? For the sake of space, let's limit the maximum range to 100,000 primes on the forum, but make it so that with just a few changes, it will extend up to the 5 million that the contest requires.

This should be fun. ;)

[cse.avinash]

For storing all prime numbers in an array its taking 9.45 seconds in my core i3 processor.
here is the code:--

#include<stdio.h>
#include<time.h>
#include<math.h>
int arr[100000000]={0};
int arr1[100000000];
int main() {
    double start,end;
    long long i,j,num,inc=2,m=0,root,q,k;
    start=clock();
     num=86028130;
    root=sqrt(num)+1;
    for(i=0;i<num;i++)arr[i]=i;
    for(i=2;i<=root;i++){
       if(arr[i]>0) {
          for(j=inc*i;j<=num;j=j+i)
            arr[j]=-1;
           inc++;
      }
    }
    for(i=0;i<num;i++) if(arr[i]>1) arr1[m++]=i;
    printf("%lld",m);
      end=clock();
      printf("\n\n%f",(end-start)/CLOCKS_PER_SEC);
     return 0;
}

when I access kth element, time exceeds.
second thing I can't use an array size of 10^8 because when I am submitting this code on that site , its showing SIGKILL error.
I can't allocate space for 10^8 long long ints. Spoj has a memory limit (256Mb) and I have crossed it.
So how to improve that i don't know .guide me sir..:(

[cse.avinash]

@Smeagel13 : I don't know 1500th prime but I also don't know 1000th prime , if I am knowing 1000th prime that means I have calculated upto 1000th prime number and same for 2000th prime number.
So can you please code your thoghts so that I can learn more.

[Smeagel13]

haha, I like Adak calling it the Smeagel plan, sounds very philosophical.

It would be slower but to get around the large array issue would be to use a linked list.
I dont know the numbers either, but you would write a small program that could run dog slow for all we care and find the 1000th, 2000th, etc... Then you take that list and initialise that boundary array (numbers to avoid) at compile time which saves time calculating them at run time.

There will be a better way of doing this, we had a competition at work, and we got our programs to do something related to a million in sub second time, granted they were run on multi million pound servers but... Ill dig the algo out, there are some good formulas which i once thought of... Nothing new, just the rules were no outside help.

[Adak]

Smeagel, you are probably outside help - but I am the counterbalance, outside interference. ;)

The wikipedia article on it (iirc), had some faster ways to test for primality, but I don't know WTH they're mathematically yakking about. I did my college age drinking at *home*! ;)

cse.avinash my idea is to go to 100,000 for this example, not 100 million. Instead of calculating the primes, they would simply be assigned to your array, and you won't need every prime. Say about every thousandth one, only.

Again, your program will not have to store every prime in an array, nor will it have to calculate all the primes, either. That's the beauty of the Smeagel plan.

I'm working on a bit of code to see how plausible the plan is. More later.

[cse.avinash]

That means few prime numbers are to be stored in an array and kth prime number is calculated with reference to that number..:-/

[Adak]

Yes. Since Q will be 50,000 queries, I have my doubts our current idea can work fast enough. Like Smeagel said, there are faster ways to do this, and he's checking into them.

What is the protocol here? You submit your program and they run it?
Your program gets input from stdin or how does that work?

[Adak]

With a spot of luck, the Smeagel plan might work yet:

I've got more testing to do, but that time of 5 seconds for 50,000 queries, INCLUDES generating a random number for each query.

So - don't act like you're not impressed. ;)

[Adak]

I tried it with the higher numbers the contest needs - just to see, and fearing the worst.

Anybody remember their history of the battle of Cannae? That was where Hannibal completely destroyed the Roman army as a fighting force.

That's what the big numbers did to my trial division program here. ;) You can stick a fork in it, trust me.

We have to use other testing for primality, and I believe cse.avinash has explored using the Sieve of Eratosthenes, which I take it were also unsuccessful.

So that leaves us with the math tests as the likely way to go.

[D33wakar]

We have to use other testing for primality, and I believe cse.avinash has explored using the Sieve of Eratosthenes, which I take it were also unsuccessful.

You guys should take a look at this.The second one is much more powerful than the first one(I'm totally amazed by the results).

[Smeagel13]

I pulled out the algorithm, i'll post most of it up when I get home.

Stats: Every prime number upto 1,000,000 took 0.9 seconds.

The main trick in that algorithm is instead of working your way up from the low numbers counting 2 everytime is to only test against previously found primes and stop when the the previously found prime is less than the square root of the number that's being tested.

To handle the big numbers, use:

primes_found = (unsigned long long *) malloc(sizeof(unsigned long long) * (MAX_TEST_NUMBER/2));

// treat as an array[]

Together with the Smeagel plan this could be good, although I'm sure there will be a formula for calculating the starting number based on any nth number, like ...

start_number = ((nth * 2) + (nth / 2));

[Adak]

Thanks Diwakar. I knew about the Sieve of Eratosthenes, but it didn't seem that fast. I know the second example author from another forum, and he's quite good.

I read on the challenge site that the Sieve of E. is too slow, unless it's "not naive".

Smeagel, I use that law of composite numbers, in my prime number program. It is a significant speed up when you get into the larger numbers, but mine takes 2.1 seconds to get to a million primes (and I use no malloc calls). You must have sprinkled some Pixie dust on that PC. ;) I look forward to seeing that code, because clearly I missed something in mine. This is the heart of my prime number generator:

/* handles all searching 5 and up */
   num = 5;                        //first regular int to test
   noprime = j = 0;
   
   for (; numPrimes < max;) {        //loop while we have < max primes
      root = (int)sqrt(num) + 1;   //test only up to sqrt of num (include math.h)
      
      for(j=0;primes[j] < root;j++ ) {  
         if (num % primes[j] == 0) {       //the test with modulo (remainder) arithmetic
            noprime = 1;           //it divided into num evenly (no remainder)
            break;                 //break out, num is not a prime number
         }
      }
      if (noprime == 0) {          //it's a prime number
         primes[numPrimes++]=num;
         //if (show == 's')
          //  printf(" %6lu ", num);
      }
      num += 2;                    //next number to be tested
      noprime = 0;                 //reset
   }

When I moved the above algorithm into a program for the challenge, it did fine for a test to find the first million, but it fell on it's face when given a random number as the kth prime to search for, with k numbers ranging up to 5 million. If you consider an average of 2.5 million as the kth prime number to find, and then time it for fifty thousand searches!! The time grows way beyond the limit of 10 seconds.

That's why I believe trial division is toast - those for loops are as small as they can be, imo. My actual trial code is messier, because it uses indexes to search only the number of primes between the primes in the primes[] array. Still, the large numbers here punish it, since none of the primes between those in the primes[] array, are known. That means I can't test only with other prime numbers, so the program is back to incrementing the testing number by just 2, and working all the way up from 3 to the sqrt of the number.

So bring on those bad boy Sieve and linear math tests, as well. I am anxious to see how they do in this challenge.

[cse.avinash]

My approach to Seives algo bit fast...take 6.5 sec to find all 5000000 prime numbers.

#include<stdio.h>
#include<time.h>
#include<math.h>
#define MAX 100000000
int arr[MAX]={0};
int arr1[5000000];
int main() {
    double start,end;
    int i,j,num,inc=2,m=0,root,q,k,cnt=0;
    start=clock();
    num=86028130;
    root=sqrt(num)+1;
    for(i=3;i<num;i+=2) arr[cnt++]=i;
    printf("%d",cnt);
    for(i=0;arr[i]<=root;i++){
                         k=arr[i];
       if(arr[i]>0) {
          for(j=i+k;j<=num;j+=k)
            arr[j]=-1;
           inc++;
      }
    }
    arr1[m++]=2;
    for(i=0;i<num;i++) if(arr[i]>1)arr1[m++]=arr[i];
     end=clock();
    printf("\n\n%f",(end-start)/CLOCKS_PER_SEC);
    return 0;
}

but it is sounding strange to me that maximum number of elements stored in arr[] is 43014064 and when I am defining MAX as 43014065, error ocuurs. don't understand why.??

[cse.avinash]

@diwakar : Yes Its very fastest approach of seive which i ve seen .

I am googling more to collect more methods, I saw segmented seive of eratosthenes but I can't understood the concept

[Adak]

That's a fast one, but leaves us with just 3.5 seconds for handling input of the k number, and output the display of 50,000 prime numbers.

Can you add a rand() % 5000000+1 to your program, and let's get an idea of the time it will take to process 50,000 queries in a loop, from this new program?

I just checked and RAND_MAX on my system is 1.07 Billion, so making these large random numbers should be no problem, but you can print out your RAND_MAX to check.

I wonder if 50K numbers can even be printed in 3.5 seconds? Hmmm... I'll test that.

On my system, it takes 3.87 seconds to just print out 50,000 numbers, between 2,250,000 and 300k. Give it a try on your system:

This function needs time.h included, as well as stdio.h

void printTest(void) {
   int i=2250000, j;
   clock_t start, stop;
   start = clock();
   for(j=0;j<50000;j++,i++) {
      printf("%d\n",i);
   }
   stop = clock();
   printf("\nThis display of 50,000 numbers being printed, one number per line, took %f seconds\n",(double) (stop-start)/CLOCKS_PER_SEC);
   getchar();
}

[cse.avinash]

ohh my god it's taking 11.3 seconds on my i3 processor.

Time is again exceeding, I need better approach to find the prime numbers, I know there is a way just to find the correct path.

[Adak]

Welcome to the Club, cse.avinash! ;)

I've located the AKS prime test on Wikipedia, so I'm going to give that a try. I know there are programs out there already for this, but I'm not interested in just copy and pasting it into an IDE for the compiler.

@Smeagel, I haven't worked with this yet, but I've seen this mentioned on a web site on primes. Is this OK or dodgy?

start_number = ((nth * 2) + (nth / 2));

Do you mean this in the normal arithmetic sense, or the digit in strings, with appending at the + sign?

[cse.avinash]

Welcome to the Club, cse.avinash!

I know there are programs out there already for this, but I'm not interested in just copy and pasting it into an IDE for the compiler.

I have not got your words..?? What are you saying adak..???

[Adak]

If you looked around enough on the internet, you could find a program that would meet this challenge.

I'm not interested in just copying somebody's program. I want to understand it enough to code my own.