Prime number printer stops at 251, why?

Question

I started learning Python today, and I came up with the idea of creating a program that prints all the prime numbers from 0 to 10 000. I managed to make my program print out all primes until 251, at which point it stops printing out numbers. Why does it do this?

Here is the code:

for numberToCheck in range(2,10000):
    divider = 2
    while numberToCheck > divider:
        if numberToCheck % divider is 0:
            break
        else:
            divider += 1
    if numberToCheck is divider:
        print(numberToCheck, "is a prime number.")

That ` (backtick) causes a syntax error. You may want to edit it and remove the ` at the end of the code section unless it is markup for formatting. — bcho04, Jun 18 '16 at 20:03
Welcome to stack overflow! In addition to your question, you could make this function about twice as efficient by not checking the modulo of the numbers greater than half of `numberToCheck`. For any given `numberToCheck`, a number greater than that number divided by two can't possibly be one of its divisors. — Alex, Jun 18 '16 at 20:07
Possible duplicate of ["is" operator behaves unexpectedly with integers](http://stackoverflow.com/questions/306313/is-operator-behaves-unexpectedly-with-integers), [Is there a difference between `==` and `is` in Python?](http://stackoverflow.com/questions/132988/is-there-a-difference-between-and-is-in-python) — hichris123, Jun 18 '16 at 21:56
@Alex can't you limit it to the square root of the number to check? — Azor Ahai -him-, Jun 18 '16 at 22:00

score 74 · Answer 1 · answered Jun 18 '16 at 20:04

The problem is that you are using is instead of ==. The is operator performs object identity comparison, which "happens to work" for all numbers below 256 due to implementation details. 251 is the biggest prime below 256 (check here, next prime is 257) and after that the is returns False:

>>> 254 + 1 is 255
True
>>> 255 + 1 is 256
True
>>> 256 + 1 is 257
False

The equality operator is ==:

>>> 254 + 1 == 255
True
>>> 255 + 1 == 256
True
>>> 256 + 1 == 257
True

Ajeet Shah · Answer 2 · 2016-06-19T00:51:52.147

Use == to check equality of numbers:

for numberToCheck in range(2,10000):
    divider = 2
    while numberToCheck > divider:
        if numberToCheck % divider is 0:
            break
        else:
            divider += 1
    if numberToCheck == divider:
        print(numberToCheck, "is a prime number.")

Is operator is used to check the id of two objects while == operator check their values.

Python implements an Array of integers for values between -5 to 256, and when you create an int object in this range, you get a reference to the existing array implementation. That's why id of all integers objects in this range is same but it is different for integers objects outside this range, as seen below:

>>> a = -6
>>> b = -6
>>> a is b      # a and b has different id
False

>>> a = -5
>>> b = -5
>>> a is b      # a and b has same id
True

>>> a = 256
>>> b = 256
>>> a is b      # a and b has same id
True

>>> a = 257
>>> b = 257
>>> a is b      # a and b has different id
False

And this is the reason, your program prints primes till 251 but not the next prime 257 and afterwards, however your program does run till numberToCheck reaches 9999.

Also, you might consider a faster algorithm to generate primes, such as Sieve of Eratosthenes.

Basically, you should check divisibility of numberToCheck with all primes between 2 and ( previously found prime or square root of numberToCheck, whichever is less ).

score 3 · Answer 3 · edited May 23 '17 at 11:45

The error is in the last if. Change it from

if numberToCheck is divider:

to

if numberToCheck == divider:

Explanation: is tests if refences are equals while == check the equality of values (more specifically it calls __eq__ method on your elements)

The reasons why you have the first primes to print up to 251 is because python cache all small integers.

For example:

>>> 100 == 10**2
True
>>> 100 is 10**2
True
>>> 1000 == 10**3
True
>>> 1000 is 10**3
False

(Example taken from here) You should use is only to check references (objects that should not only be equals but the same instance) or to compare to None.

score 3 · Answer 4 · answered Jun 18 '16 at 20:13

Never compare integers with is. Always use ==.

== should be used to compare numbers.

Here is the fixed code:

for numberToCheck in range(2,10000):
divider = 2
while numberToCheck > divider:
    if numberToCheck % divider == 0:
        break
    else:
        divider += 1
if numberToCheck == divider:
    print(numberToCheck, "is a prime number.")

score 3 · Answer 5 · edited May 23 '17 at 12:33

The problem is you used is. is doesn't check for equality, it checks for an object's identity (memory address); is object a the same as object b?

Refer to these questions:

Is there a difference between `==` and `is` in Python?

"is" operator behaves unexpectedly with integers

Why (0-6) is -6 = False?

To solve your problem:

def prime(numberToCheck):
    divider = 2
    while numberToCheck > divider:
        if numberToCheck % divider == 0:
            break
        else:
            divider += 1

        if numberToCheck == divider:
            print(numberToCheck, "is a prime number.")

A little trivial note here, but might be crucial in larger applications: I created a function called prime to maximize code re-use. Now you can pass the prime function whatever number you like to check if it's prime or not, way better than hard coding the number that you want to test!

score 2 · Answer 6 · answered Jun 18 '16 at 20:04

2

You must not compare numbers with is. Use always == for equality testing.

answered Jun 18 '16 at 20:04

Daniel

42,087
4
55
81

Isdj · Answer 7 · 2016-06-18T20:22:15.540

you are using is instead of ==. Anyhow, code wise youre wasting resources checking for primes like this. you should only check from 2 to sqrt(n) and you should preferably keep the prime numbers and check only them until you reach them, for instance youre checking if the number 41 is a prime, check prime numbers 2 3 5 and then you know it isnt a prime (because all the other numbers between the prime and the sqrt are not prime so you already checked them) create a list of primes as you go.

try this code:

import math
primes = [2]
for n in range(3,100):
    for i in primes:
        if n in primes:
            break
        if n%i == 0:
            break
        if i> math.sqrt(n):
            primes.append(n)
            break

score 2 · Answer 8 · edited May 23 '17 at 12:09

This link will help you why not to use is

In [5]: a = 254+1

In [6]: b = 255

In [7]: a is b  # both are same objects
Out[7]: True

In [8]: id(a)
Out[8]: 37644344 # id of a

In [9]: id(b)
Out[9]: 37644344   # same id as a

for > 256

In [10]: a = 256+1

In [11]: b = 257

In [12]: a is b # both are different objects but values are same
Out[12]: False

In [13]: id(a)
Out[13]: 39721992 # id of a

In [14]: id(b)
Out[14]: 39722592 # new id created not same as a

is always compares with objects not values

why only upto 256?

from python docs

The current implementation keeps an array of integer objects for all integers between -5 and 256, when you create an int in that range you actually just get back a reference to the existing object.

when you assign a=255 just you are adding a as referring excisting 255. when a=257 new int type object will be created

Prime number printer stops at 251, why?

8 Answers8