Print series of prime numbers in python

Question

I am trying to learn Python programming, and I'm pretty new at this.

I was having issues in printing a series of prime numbers from one to hundred. I can't figure our what's wrong with my code.

Here's what I wrote; it prints all the odd numbers instead of primes:

for num in range(1,101):
    for i in range(2,num):
        if (num%i==0):
            break
        else:
            print(num)
            break

Answer 1

Here's a simple and intuitive version of checking whether it's a prime in a RECURSIVE function! :) (I did it as a homework assignment for an MIT class) In python it runs very fast until 1900. IF you try more than 1900, you'll get an interesting error :) (Would u like to check how many numbers your computer can manage?)

def is_prime(n, div=2):

    if div> n/2.0: return True

    if n% div == 0:
        return False
    else:
        div+=1
        return is_prime(n,div)

#The program:
until = 1000
for i in range(until):
    if is_prime(i):
        print i

Of course... if you like recursive functions, this small code can be upgraded with a dictionary to seriously increase its performance, and avoid that funny error. Here's a simple Level 1 upgrade with a MEMORY integration:

import datetime
def is_prime(n, div=2):
    global primelist
    if div> n/2.0: return True
    if div < primelist[0]:
        div = primelist[0]
        for x in primelist:
            if x ==0 or x==1: continue
            if n % x == 0:
                return False
    if n% div == 0:
        return False
    else:
        div+=1
        return is_prime(n,div)


now = datetime.datetime.now()
print 'time and date:',now
until = 100000
primelist=[]
for i in range(until):
    if is_prime(i):
        primelist.insert(0,i)
print "There are", len(primelist),"prime numbers, until", until
print primelist[0:100], "..."

finish = datetime.datetime.now()
print "It took your computer", finish - now , " to calculate it"

Here are the resuls, where I printed the last 100 prime numbers found.

time and date: 2013-10-15 13:32:11.674448

There are 9594 prime numbers, until 100000

[99991, 99989, 99971, 99961, 99929, 99923, 99907, 99901, 99881, 99877, 99871, 99859, 99839, 99833, 99829, 99823, 99817, 99809, 99793, 99787, 99767, 99761, 99733, 99721, 99719, 99713, 99709, 99707, 99689, 99679, 99667, 99661, 99643, 99623, 99611, 99607, 99581, 99577, 99571, 99563, 99559, 99551, 99529, 99527, 99523, 99497, 99487, 99469, 99439, 99431, 99409, 99401, 99397, 99391, 99377, 99371, 99367, 99349, 99347, 99317, 99289, 99277, 99259, 99257, 99251, 99241, 99233, 99223, 99191, 99181, 99173, 99149, 99139, 99137, 99133, 99131, 99119, 99109, 99103, 99089, 99083, 99079, 99053, 99041, 99023, 99017, 99013, 98999, 98993, 98981, 98963, 98953, 98947, 98939, 98929, 98927, 98911, 98909, 98899, 98897] ...

It took your computer 0:00:40.871083 to calculate it

So It took 40 seconds for my i7 laptop to calculate it. :)

Answer 2

You are terminating the loop too early. After you have tested all possibilities in the body of the for loop, and not breaking, then the number is prime. As one is not prime you have to start at 2:

for num in xrange(2, 101):
    for i in range(2,num):
        if not num % i:
            break
    else:
        print num

In a faster solution you only try to divide by primes that are smaller or equal to the root of the number you are testing. This can be achieved by remembering all primes you have already found. Additionally, you only have to test odd numbers (except 2). You can put the resulting algorithm into a generator so you can use it for storing primes in a container or simply printing them out:

def primes(limit):
    if limit > 1:
        primes_found = [(2, 4)]
        yield 2
        for n in xrange(3, limit + 1, 2):
            for p, ps in primes_found:
                if ps > n:
                    primes_found.append((n, n * n))
                    yield n
                    break
                else:
                    if not n % p:
                        break

for i in primes(101):
    print i

As you can see there is no need to calculate the square root, it is faster to store the square for each prime number and compare each divisor with this number.

Answer 3

My way of listing primes to an entry number without too much hassle is using the property that you can get any number that is not a prime with the summation of primes.

Therefore, if you divide the entry number with all primes below it, and it is not evenly divisible by any of them, you know that you have a prime.

Of course there are still faster ways of getting the primes, but this one already performs quite well, especially because you are not dividing the entry number by any number, but quite only the primes all the way to that number.

With this code I managed on my computer to list all primes up to 100 000 in less than 4 seconds.

import time as t

start = t.clock()

primes = [2,3,5,7]

for num in xrange(3,100000,2):
    if all(num%x != 0 for x in primes):
        primes.append(num)

print primes
print t.clock() - start
print sum(primes)

Answer 4

Using filter function.

l=range(1,101)
for i in range(2,10): # for i in range(x,y), here y should be around or <= sqrt(101)
    l = filter(lambda x: x==i or x%i, l)

print l

Answer 5

Igor Chubin's answer can be improved. When testing if X is prime, the algorithm doesn't have to check every number up to the square root of X, it only has to check the prime numbers up to the sqrt(X). Thus, it can be more efficient if it refers to the list of prime numbers as it is creating it. The function below outputs a list of all primes under b, which is convenient as a list for several reasons (e.g. when you want to know the number of primes < b). By only checking the primes, it saves time at higher numbers (compare at around 10,000; the difference is stark).

from math import sqrt
def lp(b)
    primes = [2]
    for c in range(3,b):
        e = round(sqrt(c)) + 1
        for d in primes:
            if d <= e and c%d == 0:
                break
        else:
            primes.extend([c])
    return primes

Answer 6

break ends the loop that it is currently in. So, you are only ever checking if it divisible by 2, giving you all odd numbers.

for num in range(2,101):
    for i in range(2,num):
        if (num%i==0):
            break
    else:
        print(num)

that being said, there are much better ways to find primes in python than this.

for num in range(2,101):
    if is_prime(num):
        print(num)

def is_prime(n):
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True