Infinite range in my python prime finder?

Admin 1
Viewed 3540

I am trying to get an infinite range in my python prime number finder! here is my code!

import math
print "Welcome to Prime Finder!"
option = raw_input("continue(y/n)")
 if option == "y":
    for num in range(1,(infinite number)):
        if all(num%i!=0 for i in range(2,int(math.sqrt(num))+1)):
           print num

I am trying to get where it says (infinite number) to actually be an infinite number. Is there some value or something that I can use to find that? Any help would be greatly appreciated!

primes python
5 Answers

You will eventually get an overflow. Please check my code, it is a prime number generator. Just change n to the number you want to start generating primes from.

def gen_next_prime():
    n = 0
    while True:
        n += 1
        if (check_prime(n)):
            yield n

def check_prime(n):
    if n <= 3:
        return n > 1
    elif n%2 == 0 or n%3 == 0:
        return False
    i = 5
    while i*i <= n:
        if n%i == 0 or n%(i+2) == 0:
            return False
        i = i+6
    return True

g = gen_next_prime()

while True:
    key_input = input("press 'y' to get next prime ('n' to exit): ")

    if key_input == "y":
        print(next(g))
    elif key_input == "n":
        break
    else:
        print("Error! Invalid Input!")
user_107723850

What I mean below is, even if your code has an infinite range, at some point, it will be so slow that it won't seem to be doing anything at all. For me, that some point was around n=1000,000 I think.

As somebody else pointed out above, you can use a while loop and that's easy to do. Note however, that from a practical point of view, your effective range is still going to be limited, even if we ignore the fact that the time for the printing will slow processing down at some point.

I managed to analyse at most, if I recall correctly, the first million numbers, using my version of the sieve. I optimized the code quite a bit. Long story there(less than square root, only checked previous primes, used python lists (I found numpy too slow), skipped even numbers, ...) No matter how smart your code is, the amount of computation required per prime increases significantly over time. I didn't for example use parallel processing but even if I did, I think you'd get stuck fairly soon. If you were getting primes less than N^2, maybe you could sequentially compute all of the primes up to N and use that to spawn some calculations in parallel? ...

user_54640830
Related