CA _Dupin CA _Dupin - 1 month ago 12
Python Question

Efficient method for generating lists of large prime numbers

What I'm trying to figure out is when I run this code for smaller numbers it returns the list just fine, but for larger numbers (I would call this small in the context of what I'm working on.) like 29996299, it will run for a long time, I've waited for 45 minutes with no results and had to end up killing the program. What I was wondering was whether there was a more efficient way to handle numbers whose scale was larger than 4 or 5 digits. I've tested a few permutations of the range function to see if there was a better way to handle the limits of the list I want to produce but nothing seems to have any effect on the amount of time it takes to do the computation. I'm new to python and am not that experienced as a programmer. Thank you for your time.

ran the program again before submitting this post and it took an hour and a half or so.

function of the program is to take the User selected number, use it to generate a lower bound, find all primes between the bound and input and append to list, then generate a secound upper bound and find all primes and then append to list, to create a list that extends forwards and backwards from the initial number.
the program works like I expect it to but not as quickly as I need it to since the numbers I'm going to be dealing with are going to get large quickly, almost doubling at each phase.

initial_num = input("Please enter a number. ")

lower_1 = int(initial_num) - 1000
upper_1 = int(initial_num)
list_1 = []

for num in range(lower_1,upper_1):
if num > 1:
for i in range(2,num):
if (num % i) == 0:
break
else:
list_1.append(num)

lower_2 = list_1[-1]
upper_2 = list_1[-1] + 2000
list_2 = []

for num in range(lower_2,upper_2 +1):
if num > 1:
for i in range(2,num):
if (num % i) == 0:
break
else:
list_2.append(num)

list_3 = list_1 + list_2[1:]

print list_3

Answer

You can use a more efficient algorithm to generate the entire list of prime numbers up to N. This is the Sieve of Erathostenes. Please have a look at the linked article, it even includes an example pseudocode. The basic idea of the algorithm is:

  1. maintain L, a list of potentially prime numbers (initially all numbers from 2 to N)
  2. pick the next prime number (p) as the first element of L (intially 2)
  3. remove all numbers that are a multiple of p, up to N, since they cannot be prime
  4. repeat from step 2

At the end you are left with a list of prime numbers.

An implementation in Pyhton from here

def eratosthenes2(n):
    multiples = set()
    for i in range(2, n+1):
        if i not in multiples:
            yield i
            multiples.update(range(i*i, n+1, i))

print(list(eratosthenes2(100)))

To reduce memory consumpution you could consider usgin a bitset, storing one bit for each number. That should reduce memory usage by between 32 - 64 times. A bitset implementation is available for python here.