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:- 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;
}
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?
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.
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.
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.
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. ;)
@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.
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.
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..:(
@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.
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.
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.
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?
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.
