Python Print statement in a loop, generating prime numbers

Question

Where can I put a print statement to print the final list but still retain the return, and are there any ways you can think of to improve this function. I wrote the function but am unsure as to its relative quality

def buildPrimeList ():

    primeList = [1, 2]
    possiblePrime = 3
    print "To display all prime values less than or equal a number..."
    x = raw_input("Enter a number higher then 3   ")
    while (possiblePrime <= x):  
        divisor = 2
        isPrime = True

    while (divisor < possiblePrime and isPrime):
        if (possiblePrime % divisor == 0):
            isPrime = False
        divisor = divisor + 1

    if (isPrime):
        primeList.append(possiblePrime)

    possiblePrime = possiblePrime + 2

  return primeList


buildPrimeList()

score 2 · Answer 1 · edited May 23 '17 at 12:29

It's quite straight-forward to print result of a function:

print buildPrimeList()

Also I've noticed that you do not convert raw_input's result (which is string) to int:

x = int(raw_input("Enter a number higher then 3   "))

Another way to do the same thing in python might look like:

from itertools import count

def is_prime(n):
    """Checks if given number 
    n is prime or not."""

    for i in xrange(2, n/2):
        if n % i == 0:
            return False
    else:
        return True

def prime_numbers():    
    """Generator function which lazily
    yields prime numbers one by one."""

    for i in count(1):
        if is_prime(i):
            yield i

if __name__ == '__main__':

    maxprime = int(raw_input("Enter a number:"))

    for prime in prime_numbers():
        if prime < maxprime:
            print prime
        else:
            break

A number of python idioms and language features were used:

generator functions and iterators [1];
snake_case_method_naming [2];
docstrings [3];
if __name__ == '__main__': ... [4].

[1] http://www.ibm.com/developerworks/library/l-pycon/index.html

[2] PEP 8: Style Guide for Python Code

[3] http://www.learningpython.com/2010/01/08/introducing-docstrings/

[4] What does if __name__ == "__main__": do?

p.s. As jellybean and rpInt noted in their answers and comments there are a number of ways to speed things up. But most likely you shouldn't do that (unless you absolutely have to) as "Simple is better than complex" [5].

[5] PEP 20: The Zen of Python

score 1 · Answer 2 · answered Nov 08 '11 at 10:02

1

You can print the list immediately before returning it.

As for the efficency of the algorithm, consider the sieve of erathostenes.

answered Nov 08 '11 at 10:02

Johannes Charra

29,455
6
42
51

Easier to write might be to just check if a number is divisible by any of the lower, already found, primes. If it is not, it's a prime. (e.g: 3 is not divisible by 2 -> is a prime, 15 is divisible by 3, stop; 17 is not divisible by 2,3,5,7,11,13 -> is a prime). We could probably ignore those higher than half of the number we are testing but I'm not sure what would that do to the speed. – rplnt Nov 08 '11 at 10:16
2

More precisely: When looking for divisors, we can stop at the _root_ of the number we're testing, not half the number. Why are you commenting on my answer and not the original question, btw? :) – Johannes Charra Nov 08 '11 at 10:18
He was asking about the print, not about the implementation so I didn't want to post it as an answerd. And good call with the square root. Implementation and results: https://gist.github.com/1347474 – rplnt Nov 08 '11 at 10:45

score 0 · Answer 3 · answered Nov 09 '11 at 01:48

You can improve the function greatly by just taking every 2nd number and dividing by it. First, 1 isn't a prime, you shouldn't use it in that way. The reason for this is the prime factorization, that is unique for every number, like 9 = 3*3. If you would add 1 to your prime pool, 9 = 3*3, 9 = 3*3*1, 9=3*3*1*1, every one is a valid prime factorization, but it isn't unique anymore for every number. Second, you don't have to check the number with every natural number. If you think about the natural numbers, every second of them is even and divisable by 2. So, if a number is divisable by 4, it is per definition divisable by 2. You can reduce the amount of calculations you have to do by a factor of 2 if you use this property. Also, you seem to use a technique called "The Sieve of Erastothenes" http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes which just adds prime numbers to the pool, and checks if the next natural number is divisable by any of them. You can exploit that easily.

def buildPrimeList ():
    #One is not really a prime, so we cut it out.
    primeList = [2]
    possiblePrime = 3
    print "To display all prime values less than or equal a number..."
    upperlimit = raw_input("Enter a number higher then 3   ")
    try:
        upperlimit = int(upperlimit)
    except:
        print "Sorry. You didn't enter a number."
        return
    while (possiblePrime <= upperlimit):  
        #lets check if the possible prime is divisable by any prime we already know.
        isPrime = True
        for prime in primeList:
            if(possiblePrime % prime == 0):
                #we can abort the check here, since we know already that this number can't be a prime
                isPrime = False
                break

        if (isPrime):
            primeList.append(possiblePrime)

        possiblePrime = possiblePrime + 2

    return primeList


print buildPrimeList()

This should work as expected.

Python Print statement in a loop, generating prime numbers

3 Answers3