3
\$\begingroup\$

I have just started using Python, and I am attempting to make a prime number sequence generator, where it will print the a specified amount prime numbers in terminal. I have other versions of this also, and versions for the Fibonacci sequence, although, I will post just the version for prime numbers I specified above.

    P = 2
    Count = 1
    X = int(raw_input('choose number: '))

    def Main(P, X):
        while Count <= X:
            isprime = True
            for x in range(2, P - 1):
                if P % x == 0: 
                    isprime = False
            if isprime:
                print P
                Count += 1
            P += 1

I am currently trying to optimize this code so that it runs as fast as possible, and then making small edits. I did this by putting a get daytime now function at the beginning and the end of the sequence generator, and printing the time, then looping it all a specified amount of times.

from datetime import datetime as dt

P = 2
Count = 1
Count2 = 1
X = int(raw_input('choose number: '))

def Main(P, Count, X):
    t1 = dt.now()
    while Count <= X:
        isprime = True
        for x in range(2, P - 1):
            if P % x == 0: 
                isprime = False
        if isprime:
            Count += 1
        P += 1
    t2 = dt.now()
    print ((t2-t1).microseconds)

while Count2 <= 20:
    Main(P, Count, X)
    Count2 += 1

As far as my knowledge of Python extends, I have optimized this code so it runs quite efficiently. However, I want to know if anyone can help make this code any better, however, it needs to stay within one function (two if necessary), and it does the same type of thing. Also, if it is possible to explain why it does better, that would be appreciated. However, any comment or feedback would be nice.

\$\endgroup\$
  • \$\begingroup\$ Never, never use capital letters for variables (P, X, Count) or function names (Main). Only for classes (CamelCase), or constants (all uppercase with underscores and digits). See PEP-8. Also, give your functions meainingful names (Main is the worst possible name, generate_primes is better) \$\endgroup\$ – smci May 5 at 3:31
7
\$\begingroup\$

A logical optimization here would be to remember the primes you have already calculated. Consider the theory:

A prime is a number that is divisible by itself and 1 only

It follows that, to test if any number X is prime, you only need to find 1 prime number less than X which divides in to X without a remainder. There is no need to test non-prime numbers, because if a non-prime divides cleanly in to X, then the prime factors would also divide in to X.

So, if you keep a record of the previously calculated primes, then you only need to scan those values to see if they divide in to X. In essence, each time you print a prime, also add it to a list.

This will require 'seeding' the prime list with the value 2.

A second optimization is that a number X is only prime if it has a factor. A factor is a number, multiplied by another number, that is equal to the original value X.

The useful theory here, is that, as the value of the first factor increases, the value of the second factor decreases. There is a point when the first and second factors 'cross over' and the second factor becomes less than the first.

The cross-over point is the square-root of the number X. When you pass the square-root of the number, you have tested all the possible factors... there's no need to scan values larger than the root, because, if they were factors, you would have found them already by identifying the small factor that matches the larger factor.

Putting these two items together, you should modify your code to:

  1. Have a special case for 2, which is prime, and store it in the seed array.
  2. preserve the prime numbers you find in the same array.
  3. for values larger than 2, you only need to use values from the pre-identified prime array to test for factors
  4. you only need to look for prime factors that are less than, or equal to the square-root of the value.
\$\endgroup\$
  • \$\begingroup\$ "a number X is only prime if it has a factor" - Presumably that should be "doesn't have"? \$\endgroup\$ – Holloway Dec 23 '14 at 11:33
5
\$\begingroup\$

As rolfl has given an excellent review of the algorithm, I'll focus on the actual code you have provided.

Style

Your variables and functions names are not quite compliant to PEP 8, the Python style guide.

count, p, main, etc would probably be better. Also, main is not a good name, generate_prime might be better.

Also, what you are doing with Count2 could be more simply done with a single for loop. Because the number we are using for iterations is not used, the convention is to call it _ and we have : for _ in range(20) which will perform whatever you want to do 20 times.

At this point, your code looks like :

from datetime import datetime as dt

def generate_primes(p, count, x):
    t1 = dt.now()
    while count <= x:
        isprime = True
        for i in range(2, p - 1):
            if p % i == 0:
                isprime = False
        if isprime:
            count += 1
        p += 1
    t2 = dt.now()
    # Commented for testing purposes : print ((t2-t1).microseconds)

if __name__ == "__main__":
    p = 2
    count = 1
    x = 11 # Commented for testing purposes : int(raw_input('choose number: '))
    for _ in range(20):
        generate_primes(p, count, x)

Decomposition in functions

You have a piece of code testing whether a number is a prime number or not. This could easily be extracted into a function on its own that you'll be able to re-use and/or optimise later on.

def is_prime(n):
    isprime = True
    for i in range(2, n - 1):
        if n % i == 0:
            isprime = False
    return isprime

def generate_primes(p, count, x):
    t1 = dt.now()
    while count <= x:
        if is_prime(p):
            print(p)
            count += 1
        p += 1
    t2 = dt.now()
    # Commented for testing purposes : print ((t2-t1).microseconds)

Global variables

At the moment, your main function uses global variables which makes it quite hard to follow what it is supposed to do and hard to test.

It seems like you are trying to do multiple things with this variables : keeping track of a count, checking a limit and keeping track of the number you have to consider. This is quite a lot to handle for a function.

Python has a pretty cool feature which could help you write things in a better way : generators. We can define a kind of function that will generate a new prime number every time we call it and then just call it the right amount of times.

You can iterate over the result of such a function just like you iterate over a container but you have to remember that it will not end except if you do it explicitly.

For instance, you'd have something like :

def generate_primes():
    p = 2
    while True: # never ending loop
        if is_prime(p):
            yield p
        p += 1


i = 0
for p in generate_primes():
    print(p)
    i+=1
    if i == 10:
        break

We have separated the concerns : on one hand, we have a prime generator, on the other hand, some logic to count them.

Now that you have the basic, we can improve this. We can for instance, use zip and range to ensure we take only a finite number of elements from our prime generator.

for i, p in zip(range(10), generate_primes()):
    print(i, p)

Also, in the function itself, we could use itertools.count to go through values of p in a faster and more concise way.

Your code now looks like :

from datetime import datetime as dt
import itertools

def is_prime(n):
    isprime = True
    for i in range(2, n - 1):
        if n % i == 0:
            isprime = False
    return isprime

def generate_primes():
    for p in itertools.count(2):
        if is_prime(p):
            yield p

if __name__ == "__main__":
    lim = 11 # Commented for testing purposes : int(raw_input('choose number: '))
    for _ in range(20):
        t1 = dt.now()
        zip(range(10), generate_primes())
        t2 = dt.now()
        print ((t2-t1).microseconds)

Various optimisations

As a reference, currently, generating 1000 primes on my config takes about 366000 micro-seconds.

In is_prime, as soon as you have set isprime = False, you can return from the function as it will never go back to True. You can simply remove the variable and call return directly :

def is_prime(n):
    for i in range(2, n - 1):
        if n % i == 0:
            return False
    return True

I just realised that because you are using Python 2, you can simply call xrange instead of range as you do not need to generate a list. Run-time is down to 146000.

Now, if n is not a prime, a least one divisor will be smaller or equal to its square-root. Thus, you can just go like this :

import math

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

Running-time is down to 7000.

As you iterate looking for primes, you know that except for 2, they will all be odd numbers. You can generate 2 and then go through odd numbers only :

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

def generate_primes():
    yield 2
    for p in itertools.count(3, 2):
        if is_prime(p):
            yield p

Running time is now down to 6000.

\$\endgroup\$
  • \$\begingroup\$ Also... PyPy! PyPy gives a 5x speed improvement. \$\endgroup\$ – Veedrac Dec 24 '14 at 22:42
  • \$\begingroup\$ 1 + int(math.sqrt(n) is unnecessary, you can use 1 + math.floor(math.sqrt(n)) \$\endgroup\$ – smci May 5 at 3:36
  • \$\begingroup\$ @smci Interesting! Do you know the pros and cons? (I've used the exact same snippet in various places in my code but I may go for your version if it is better) \$\endgroup\$ – Josay May 6 at 21:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.