What's the issue with this 1000th prime number code?

Question

count=5 #Nth prime number
i=10  #number to be checked
while (count!=1000):  #until its not 1000th
 if i%2==0 or i%3==0 or i%5==0 or i%7==0:  #to check non prime
  i=i+1 #next number initialized
 else: #for prime
  count=count+1 #move to next position
if count==1000: #if is 1000th position 
 print i," is 1000th prime." #print prime

I am considering 2,3,5,7 are already known as prime and starting from 10.

It gives "11 is 1000th prime" as output. There is a logical error somewhere, I guess.

I think you're supposed to to tell us what is wrong with this — OneCricketeer, Jul 06 '17 at 01:58
You're counting as a prime any number that is not divisible by 2,3,5, or 7, but there are many non-primes that aren't divisible by any of these . You would need to check against all primes found so far. — perigon, Jul 06 '17 at 01:59
121. 221. Take any two primes larger than 7 and multiply them together. — perigon, Jul 06 '17 at 02:05
@user55449 That's a point, but then it would need storing all primes calculated till then? — Zircoz, Jul 06 '17 at 02:08
Well, yes. Nobody said finding primes was a computationally cheap problem. — perigon, Jul 06 '17 at 02:09
Final else ain't creating issue. Converting it to if did nothing new. — Zircoz, Jul 06 '17 at 02:18
Just think a bit about what will happen inside the loop when i is 11. How will it ever get to 12? — happydave, Jul 06 '17 at 02:19

score 3 · Accepted Answer · answered Jul 06 '17 at 02:19

3

As others have mentioned in comments, your criteria for deciding if a number is prime is very wrong. You're only testing whether it's divisible by the first 4 primes, but this is not sufficient for numbers larger than 120 (121 is divisible by 11, but not any of the smaller primes). You need to check all the primes found previously (look up "Sieve of Eratosthenes").

The other problem is that you're not incrementing i when the number is prime. So once you get to 11, you keep incrementing count, but not i. When count gets to 1000 you print i as the 1,000th prime. Take i = i + 1 out of the if block, it should be done every time.

Also, since even numbers can never be prime (except for 2), you can start with i = 11 and increment it by 2 -- don't waste time checking the even numbers. And then you can take i % 2 == 0 out of the test.

answered Jul 06 '17 at 02:19

Barmar

741,623
53
500
612

Also, checking against all numbers till i will work instead of storing all primes? – Zircoz Jul 06 '17 at 02:26
@user8262214 That will work, but it's extremely inefficient for very large numbers. – Barmar Jul 06 '17 at 02:29
You only need to check numbers smaller than `sqrt(i)`. – Barmar Jul 06 '17 at 02:29
Alright! Thank You! – Zircoz Jul 06 '17 at 02:30

score 1 · Answer 2 · answered Jul 06 '17 at 02:20

The logic you write to calculate prime number is wrong. I think you can store all prime number you calculated in previous test then test next number by dividing all previous prime number or just test next number simply according to the definition of prime number
In loop, if i == 11, then you will increase counter, however, i won't be increased, so for following loops, you will just test if 11 is the prime number. That's why you print 11 as 1000th number. Actually, you will print 11 as Nth prime number. I think you should always increase i.

Esteban Martinena Guerrero · Answer 3 · 2017-07-06T03:27:27.210

143 is 11*13 so its not prime. Your code would count it as prime because you only check if it can be divided by the first 5 prime numbers. To resolve your doubt I just multiplied the next to primes 11 and 13. Hope it helps.

By the way your code is also wrong because it only increments "i" when it match the condition, so when it s always checking: if 11%2==0 or 11%3==0 or 11%5==0 or 11%7==0:

Solution for your code (doesn't calculate the 1000th prime):

count=5 #Nth prime number
i=10  #number to be checked
while (count!=1000):  #until its not 1000th
    if i%2==0 or i%3==0 or i%5==0 or i%7==0:  #to check non prime
        pass #next number initialized
    else: #for prime
        count=count+1 #move to next position
    i=i+1
if count==1000: #if is 1000th position 
    print i-1," is 1000th prime." #print prime

Solution for your problem:

def is_prime(n):
  if n == 2 or n == 3: return True
  if n < 2 or n%2 == 0: return False
  if n < 9: return True
  if n%3 == 0: return False
  r = int(n**0.5)
  f = 5
  while f <= r:
    if n%f == 0: return False
    if n%(f+2) == 0: return False
    f +=6
  return True

count=5 #Nth prime number
i=10  #number to be checked
while (count!=8):  #until its not 1000th
    if not is_prime(i):  #to check non prime
        pass #next number initialized
    else: #for prime
        count=count+1 #move to next position
    i=i+1
if count==8: #if is 1000th position
    print i-1," is 1000th prime." #print prime

Function is_prime(n) got from isPrime Function for Python Language

This isn't sufficient, because then you don't catch 17*19 - and so on. There isn't a hard-codeable workaround here. — perigon, Jul 06 '17 at 02:10
This doesn't explain why it says that `11` is the 1,000th prime. — Barmar, Jul 06 '17 at 02:10
Even with this error, 11 is only the 5th prime. It should print some large non-prime as the 1,000th prime, not 11. — Barmar, Jul 06 '17 at 02:11

What's the issue with this 1000th prime number code?

3 Answers3