Find out the 20th, 30th, nth number. (I get the 20th, but not the 30s?) [Python]

Question

The question is to find the 1000th prime. For this, I wrote the following code for python. The problem is that I get the correct answer for the 10th, 20th day, but after that every increment of 10 leaves me aside from the mark. I can not catch the error here :(

count=1 #to keep count of prime numbers primes=() #tuple to hold primes candidate=3 #variable to test for primes while count<20: for x in range(2,candidate): if candidate%x==0: candidate=candidate+2 else : pass primes=primes+(candidate,) candidate=candidate+2 count=count+1 print primes print "20th prime is ", primes[-1] 

If you're interested, the score is initialized to 1 because I am not testing 2 as a prime (I start with 3), and candidate incremented by 2 because only odd numbers can be the first numbers. I know that there are other ways to solve this problem, such as the prime number theorem, but I want to know what is wrong with this approach. Also, if there are any considerations you have in mind, please suggest.

thanks

Answer 1

In test_generators.py there is a good Eratosthenes sieve Implementation :

 def intsfrom(i): while 1: yield i i += 1 def firstn(g, n): return [g.next() for i in range(n)] def exclude_multiples(n, ints): for i in ints: if i % n: yield i def sieve(ints): prime = ints.next() yield prime not_divisible_by_prime = exclude_multiples(prime, ints) for p in sieve(not_divisible_by_prime): yield p primes = sieve(intsfrom(2)) >>> print firstn(primes, 20) [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71] 

Answer 2

There are many (!) That need to be improved with Python code, but to answer your specific question:

When you find divisor ( candidate % x == 0 ), you increase the candidate, but do nothing about x . This can lead to two problems:

• candidate may have a divisor, but it is smaller than any x that is being tested, because testing at the next iteration of the loop starts with x , which used to be higher than x not by 2 .
• candidate may have a divisor, but it is bigger than x ever because you take x from 2 to candidate when you start the loop.

Answer 3

I do not think this checks what you think it is testing. It looks like you're trying to say "for every number from 2 to my candidate, check to see if the candidate is equally divided by that number." However, when you find the prime (candidate% x == 0), you only increase the candidate - you still need to start the "for x in ..." cycle again, as the candidate has changed.

What I see from the code as written; Of course, there are many other ways and other optimizations to use here.

Answer 4

It is good to know that every prime number greater than 3 can be written as: 6k-1 / + 1.

When you are looking for the next candidate, you can always write something like this (the code snippet is in C):

 a=1; ... candidate=6*k+(a=(a==-1)?1:-1); if(a==1){ k++; } 

And the function that I used not so long ago to determine the nth prime number, where LIM is the nth number you are looking for (C code):

 int sol2(){ int res,cnt,i,k,a; res=-1; i=1; cnt=3; k=1; a=1; while (1){ if (util_isprime(cnt)){ i++; if (i==LIM){ res=cnt; break; } } /* 6k+/-1 starting from 6*1-1 */ cnt=6*k+(a=(a==-1)?1:-1); if(a==1){ k++; } } return res; } 

Answer 5

in the instructions:

 for x in range(2,candidate) 

you can reduce the number of iterations by scanning to sqrt (candidate)

If the candidate is divisible by x, then we can write the candidate = x * b for some b. If x is less than or equal to b, then x must be less than or equal to the square root of the candidate

Answer 6

As for optimizations, if you are sure that you want to follow this implementation, you can not look at the numbers that:

• end in 5 since they are divided by 5.
• consist of the same numbers, for example. 22, 33, 44, 55, 66, etc., since they are divided by 11.

Remember to add 5 and 11 as simple ones though!

Answer 7

If I'm not mistaken, you always add the current candidate to the list of primes, regardless of whether a divisor is found or not. Your code for adding to the list of primes (postponing the comment of an immutable tuple made earlier) goes beyond the test for integer divisors and therefore always starts.

Answer 8

If you want something remotely effective, make an "Eratosthenes sieve" - it is as simple as it is.

 MAX = 10000 candidates = [True] * MAX candidates[0] = False candidates[1] = False primelist = [] for p,isprime in enumerate(candidates): if isprime: primelist.append(p) for n in range(2*p,MAX,p): candidates[n] = False print primelist[1001] 

Answer 9

FYI ... I solved this with the following code, although it can be optimized much more, I just decided to solve it this way first. Thank you all for your help.

 from math import * primes=[2,3] count=2 testnumber=5 while count<1000: flag=0 for x in range(2,testnumber): if x<=sqrt(testnumber): if testnumber%x==0: #print testnumber , "is not a prime" flag=1 else : pass if flag!=1: #print testnumber , "is a prime" primes=primes+[testnumber] count=count+1 testnumber=testnumber+2 #print primes print "1000th prime is ", primes[-1] 

Now I will look at all the other algorithms that you all mentioned

Answer 10

c beginner

 #include<stdio.h> int main () { int a,s,c,v,f,p,z; while(scanf("%d",&f) !=EOF){ p=0; for(z=1;p<f;z++){ s=2; a=z; while(s<a){ if(a%s==0)s=a+1; else s=s+1; } if (s!=a+1)p++; } printf("%d\n",a); } return 0; }