@@ -58,6 +58,38 @@ def primes(max: int) -> Generator[int, None, None]:
5858 yield i
5959
6060
61+ def fast_primes (max : int ) -> Generator [int , None , None ]:
62+ """
63+ Return a list of all primes numbers up to max.
64+ >>> list(fast_primes(0))
65+ []
66+ >>> list(fast_primes(-1))
67+ []
68+ >>> list(fast_primes(-10))
69+ []
70+ >>> list(fast_primes(25))
71+ [2, 3, 5, 7, 11, 13, 17, 19, 23]
72+ >>> list(fast_primes(11))
73+ [2, 3, 5, 7, 11]
74+ >>> list(fast_primes(33))
75+ [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]
76+ >>> list(fast_primes(10000))[-1]
77+ 9973
78+ """
79+ numbers : Generator = (i for i in range (1 , (max + 1 ), 2 ))
80+ # It's useless to test even numbers as they will not be prime
81+ if max > 2 :
82+ yield 2 # Because 2 will not be tested, it's necessary to yield it now
83+ for i in (n for n in numbers if n > 1 ):
84+ bound = int (math .sqrt (i )) + 1
85+ for j in range (3 , bound , 2 ):
86+ # As we removed the even numbers, we don't need them now
87+ if (i % j ) == 0 :
88+ break
89+ else :
90+ yield i
91+
92+
6193if __name__ == "__main__" :
6294 number = int (input ("Calculate primes up to:\n >> " ).strip ())
6395 for ret in primes (number ):
@@ -66,5 +98,24 @@ def primes(max: int) -> Generator[int, None, None]:
6698 # Let's benchmark them side-by-side...
6799 from timeit import timeit
68100
69- print (timeit ("slow_primes(1_000_000)" , setup = "from __main__ import slow_primes" ))
70- print (timeit ("primes(1_000_000)" , setup = "from __main__ import primes" ))
101+ print (
102+ timeit (
103+ "slow_primes(1_000_000_000_000)" ,
104+ setup = "from __main__ import slow_primes" ,
105+ number = 1_000_000 ,
106+ )
107+ )
108+ print (
109+ timeit (
110+ "primes(1_000_000_000_000)" ,
111+ setup = "from __main__ import primes" ,
112+ number = 1_000_000 ,
113+ )
114+ )
115+ print (
116+ timeit (
117+ "fast_primes(1_000_000_000_000)" ,
118+ setup = "from __main__ import fast_primes" ,
119+ number = 1_000_000 ,
120+ )
121+ )
0 commit comments