# Two versions of Socratica's prime number generator

Oct 27th, 2021 (edited)
911
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. import itertools
2.
3.
4. # The original from the video
5. def prime_numbers1():
6.     # Handle the first prime
7.     yield 2
8.     prime_cache = [2]  # Primes we've already found
9.
10.     # Loop over positive, odd integers
11.     for n in itertools.count(3, 2):
12.         # Assume prime until proven otherwise
13.         is_prime = True
14.
15.         # Check to see if any prime number divides n
16.         for p in prime_cache:
17.             if n % p == 0:  # p divides n evenly
18.                 is_prime = False
19.                 break
20.
21.         if is_prime:
22.             prime_cache.append(n)
23.             yield n
24.
25.
26. # My modified, much more efficient version
27. def prime_numbers2():
28.     # Handle the first prime
29.     yield 2
30.     prime_cache = [2]  # Primes we've already found
31.
32.     # Loop over positive, odd integers
33.     for n in itertools.count(3, 2):
34.         # Assume prime until proven otherwise
35.         is_prime = True
36.
37.         # Check to see if any prime number divides n
38.         for p in prime_cache:
39.             quotient, remainder = divmod(n, p)
40.             if remainder == 0:  # p divides n evenly
41.                 is_prime = False
42.                 break
43.             if quotient <= p:  # p**2 >= n
44.                 is_prime = True
45.                 break
46.
47.         if is_prime:
48.             prime_cache.append(n)
49.             yield n
50.
51.
52. def primes_up_to(n, primegen):
53.     lst = []
54.     for p in primegen:
55.         if p > n:
56.             return lst
57.         lst.append(p)
58.
59.
60. # In [1]: %timeit primegen.primes_up_to(200000, primegen.prime_numbers1())
61. # 7.03 s ± 15.5 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
62.
63. # In [2]: %timeit primegen.primes_up_to(200000, primegen.prime_numbers2())
64. # 160 ms ± 1.07 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
65.
RAW Paste Data