import math
from collections.abc import Generator


def SCREAMING_SNAKE_CASE				(     lowercase_:	int				):
       _UpperCamelCase     :       Generator  						=  (i for i in range(1		,						(max_n + 1)				))
       for i in (n for n in numbers if n > 1):
              for j in range(2		,						lowercase_				):
                     if (i % j) == 0:
                            break
              else:
                     yield i


def SCREAMING_SNAKE_CASE				(     lowercase_:	int				):
       _UpperCamelCase     :       Generator  						=  (i for i in range(1		,						(max_n + 1)				))
       for i in (n for n in numbers if n > 1):
              # only need to check for factors up to sqrt(i)
              _UpperCamelCase     :       Any  						=  int(math.sqrt(lowercase_				)				) + 1
              for j in range(2		,						lowercase_				):
                     if (i % j) == 0:
                            break
              else:
                     yield i


def SCREAMING_SNAKE_CASE				(     lowercase_:	int				):
       _UpperCamelCase     :       Generator  						=  (i for i in range(1		,						(max_n + 1)		,						2				))
       # It's useless to test even numbers as they will not be prime
       if max_n > 2:
              yield 2  # Because 2 will not be tested, it's necessary to yield it now
       for i in (n for n in numbers if n > 1):
              _UpperCamelCase     :       Tuple  						=  int(math.sqrt(lowercase_				)				) + 1
              for j in range(3		,						lowercase_		,						2				):
                     # As we removed the even numbers, we don't need them now
                     if (i % j) == 0:
                            break
              else:
                     yield i


def SCREAMING_SNAKE_CASE				(     ):
       from timeit import timeit

       _UpperCamelCase     :       Optional[Any]  						=  'from __main__ import slow_primes, primes, fast_primes'
       print(timeit('slow_primes(1_000_000_000_000)'		,						setup=lowercase_		,						number=1000000				)				)
       print(timeit('primes(1_000_000_000_000)'		,						setup=lowercase_		,						number=1000000				)				)
       print(timeit('fast_primes(1_000_000_000_000)'		,						setup=lowercase_		,						number=1000000				)				)


if __name__ == "__main__":
 UpperCAmelCase					=				int(input('''Calculate primes up to:\n>> ''').strip())
 for ret in primes(number):
  print(ret)
 benchmark()




from __future__ import annotations


def SCREAMING_SNAKE_CASE				(     lowercase_:	int		,						lowercase_:	int		,						lowercase_:	int				):
       assert (
           c % greatest_common_divisor(lowercase_		,						lowercase_				) == 0
       )  # greatest_common_divisor(a,b) function implemented below
       ((_UpperCamelCase)						,      (_UpperCamelCase)						,      (_UpperCamelCase))     :       int  						=  extended_gcd(lowercase_		,						lowercase_				)  # extended_gcd(a,b) function implemented below
       _UpperCamelCase     :       List[Any]  						=  c / d
       return (r * x, r * y)


def SCREAMING_SNAKE_CASE				(     lowercase_:	int		,						lowercase_:	int		,						lowercase_:	int		,						lowercase_:	int = 2				):
       ((_UpperCamelCase)						,      (_UpperCamelCase))     :       Tuple  						=  diophantine(lowercase_		,						lowercase_		,						lowercase_				)  # Initial value
       _UpperCamelCase     :       List[Any]  						=  greatest_common_divisor(lowercase_		,						lowercase_				)
       _UpperCamelCase     :       Optional[int]  						=  a // d
       _UpperCamelCase     :       Optional[Any]  						=  b // d

       for i in range(lowercase_				):
              _UpperCamelCase     :       Union[str, Any]  						=  xa + i * q
              _UpperCamelCase     :       List[Any]  						=  ya - i * p
              print(lowercase_		,						lowercase_				)


def SCREAMING_SNAKE_CASE				(     lowercase_:	int		,						lowercase_:	int				):
       if a < b:
              _UpperCamelCase						,      _UpperCamelCase     :       Optional[Any]  						=  b, a

       while a % b != 0:
              _UpperCamelCase						,      _UpperCamelCase     :       Union[str, Any]  						=  b, a % b

       return b


def SCREAMING_SNAKE_CASE				(     lowercase_:	int		,						lowercase_:	int				):
       assert a >= 0 and b >= 0

       if b == 0:
              _UpperCamelCase						,      _UpperCamelCase						,      _UpperCamelCase     :       Optional[Any]  						=  a, 1, 0
       else:
              ((_UpperCamelCase)						,      (_UpperCamelCase)						,      (_UpperCamelCase))     :       Any  						=  extended_gcd(lowercase_		,						a % b				)
              _UpperCamelCase     :       Any  						=  q
              _UpperCamelCase     :       str  						=  p - q * (a // b)

       assert a % d == 0 and b % d == 0
       assert d == a * x + b * y

       return (d, x, y)


if __name__ == "__main__":
 from doctest import testmod

 testmod(name='''diophantine''', verbose=True)
 testmod(name='''diophantine_all_soln''', verbose=True)
 testmod(name='''extended_gcd''', verbose=True)
 testmod(name='''greatest_common_divisor''', verbose=True)



