Prime Number Sequence generator

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.

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:

• Have a special case for 2, which is prime, and store it in the seed array.

• preserve the prime numbers you find in the same array.

• for values larger than 2, you only need to use values from the pre-identified prime array to test for factors

• you only need to look for prime factors that are less than, or equal to the square-root of the value.

StackExchange Code Review Q#74550, answer score: 7