prime number generator in python: accumulation of numbers

Question

My generator works great: I've tested it many times. Only, there is a problem: as the numbers increase, as one might believe, the program becomes slower. I have thought up of a way to do this, but don't know how, as I have only started with python not too long ago.

My generator looks like this:

    while 0==0:
        i=input('Enter the number for which all previous shall be tested for primality: ')
        n=0
        a=[0,1,2]
        while n<=i:
            n=n+1
            for b in range(2,n):
                if n%b==0:
                    break
                if b==(n-1):
                    a.append(n)
                    print a`

I have found that if I move the a=[0,1,2] to the space before while 0==0, it accumulates all numbers from previous uses while the program is running. What i want to change about this is that as a accumulates prime numbers, it uses those to catch up to the next unknown number. For example, lets say that I wanted all of the prime numbers up to 100. Then, I wanted all of the prime numbers up to 200. Instead of recalculating the prime numbers up to 100, I want to program to skip those and continue from the first prime number after 100.

Any advice will be really appreciated, and I am using 2.7 Python.

a = [2,3,5,7,11]
while 1:
    b = input('Enter the number for which all previous shall be tested for primality: ')
    c = len(a)
    d = 0
    isprime = True
    while b<=a[c-1] and not d==c:
            if b==a[d]:
            print a[0:d]
        if d==(c-1) and not b==a[d]:
            break
        d = d + 1
    while b>a[c-1]:
        d = 0
        print a[c-1]
        if b%a[d]==0:
            isprime = False
            break
        while a[d]==a[c-1]:
            f = a[c-1] + 2
            for g in range(f,b,2):
                if b%g==0:
                    isprime = False
                    break
            if isprime:
                a.append(b)
                print a

Alright, I made this program to work so that as the prime numbers are found, they are stored and used for the next set of prime numbers. With this let's say that I wanted to find the primes up to 1000. The program computes the primes. Then, I want to know the primes up to 2000. Well, since the program has already found the primes up to 1000, no need to reproduce them, so it takes all of the prime less than or equal to the highest number is the input, then finds what is left by dividing the new numbers by the known primes. It then adds the new primes to a, and continues.

Only thing is, there is a problem. It doesn't want to work the way I planned, and I am working on trying to fix it. Maybe you guys can pitch in and see what is wrong?

Alright, i have edited the code so that it runs faster:

While 1:
    i=input('Enter the number for which all previous shall be tested for primality: ')
    n=0
    while n<=i:
        n=n+1
        a=int(n**.5)
        for b in range(2,n):
            if n%b==0:
                break
             if b==a:
                print n
                break

So far, this program runs in the fraction of the time as my original and those that i have tried. In a test I preformed, I had it and my first algorithm find all primes to 100000. My first algorithm took a tad bit over 4 minutes, unlike my new program, which took approximately 1 minute and 40 seconds. Quite the upgrade, if I may say so myself.

Answer 1

There are various prime number algorithms, of which sieves are the fastest. If you're familiar with extending python with c, you can wrap primesieve. Below is a python implementation of the sieve of Eratosthenes, let me know if you have further problems:

from __future__ import generators
def eratosthenes():
    '''Yields the sequence of prime numbers via the Sieve of Eratosthenes.'''
    D = {}  # map composite integers to primes witnessing their compositeness
    q = 2   # first integer to test for primality
    while 1:
        if q not in D:
            yield q        # not marked composite, must be prime
            D[q*q] = [q]   # first multiple of q not already marked
        else:
            for p in D[q]: # move each witness to its next multiple
                D.setdefault(p+q,[]).append(p)
            del D[q]       # no longer need D[q], free memory
        q += 1

Answer 2

This should work faster:

while 1:
    i=input('Enter the number for which all previous shall be tested for primality: ')
    n=5
    a=[2,3]
    while n<=i:
        n=n+1
        isPrime = True
        for b in a:
            if n%b==0:
                isPrime = False
                break
        if isPrime:
            a.append(n)
            print a

But I do not think you can get much faster that O(See comment of sebastian) except if you are using more advanced algorithms and numbers very huge 10**100.

It will always get slower with bigger numbers.