prime sieve

prime sieve

import random

sieve_scan_top = 0
sieve = {}

def generate_sieve(top):
  global sieve_scan_top
	global sieve
	if top > sieve_scan_top:
		sieve_scan_top = top
		sieve = {}
		for i in range(2, top + 1):
			#might as well skip most common multiples
			sieve[i] = True
		i = 2
		while i < top:
			if i in sieve:
				deleted = 0
				j = i
				product = j * i
				while product <= top:
					if product in sieve:
						deleted += 1
						del sieve[product]
					j += 1
					product = i * j
			i += 1

def is_prime(num):
	generate_sieve(num)
	return num in sieve

def generate_prime(min_bound=2, max_bound=1000000):
	generate_sieve(max_bound)
	result = random.randint(min_bound, max_bound)
	while not is_prime(result):
		result = random.randint(min_bound, max_bound)
	return result