这应该工作得更快:

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

但我不认为你能比 O 快得多(见塞巴斯蒂安的评论)，除非你使用更高级的算法和非常庞大的数字 10**100.

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.