Advertisement
Omnifarious

Two versions of Socratica's prime number generator

Oct 27th, 2021 (edited)
1,082
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.75 KB | None | 0 0
  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.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement