




"""simple docstring"""





import math
from collections.abc import Generator

def 						lowerCAmelCase							(	lowerCamelCase						):
						'''simple docstring'''


						snake_case__    :   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 ,     lowerCamelCase						):
																		if (i % j) == 0:
																								break
												else:
																		yield i

def 						lowerCAmelCase							(	lowerCamelCase						):
						'''simple docstring'''


						snake_case__    :   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)
												snake_case__    :   Dict							     =   int(math.sqrt(lowerCamelCase						)						) + 1
												for j in range(2 ,     lowerCamelCase						):
																		if (i % j) == 0:
																								break
												else:
																		yield i

def 						lowerCAmelCase							(	lowerCamelCase						):
						'''simple docstring'''


						snake_case__    :   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):
												snake_case__    :   Optional[int]							     =   int(math.sqrt(lowerCamelCase						)						) + 1
												for j in range(3 ,     lowerCamelCase ,     2						):
																		# As we removed the even numbers, we don't need them now
																		if (i % j) == 0:
																								break
												else:
																		yield i

def 						lowerCAmelCase							(	):
						'''simple docstring'''


						from timeit import timeit

						snake_case__    :   List[str]							     =   '''from __main__ import slow_primes, primes, fast_primes'''
						print(timeit('''slow_primes(1_000_000_000_000)''' ,     setup=lowerCamelCase ,     number=1000000						)						)
						print(timeit('''primes(1_000_000_000_000)''' ,     setup=lowerCamelCase ,     number=1000000						)						)
						print(timeit('''fast_primes(1_000_000_000_000)''' ,     setup=lowerCamelCase ,     number=1000000						)						)


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








"""simple docstring"""





class  __lowercase    :


				'''simple docstring'''


				class  __lowercase    :


								'''simple docstring'''


								_lowerCAmelCase		     ="_prev", "_data", "_next"

								def __init__(				self				:       List[Any] ,SCREAMING_SNAKE_CASE_				:       int ,SCREAMING_SNAKE_CASE_				:       Union[str, Any] ,SCREAMING_SNAKE_CASE_				:       Any ):
														snake_case__    :   Any							     =   link_p
														snake_case__    :   List[str]							     =   element
														snake_case__    :   str							     =   link_n





								def  _lowerCamelCase   (				self				:       Optional[Any] ):
														return (
														    F''' Prev -> {self._prev is not None}, Next -> {self._next is not None}'''
														)







				def __init__(				self				:       Any ):
										snake_case__    :   int							     =   self._Node(SCREAMING_SNAKE_CASE_ ,SCREAMING_SNAKE_CASE_ ,SCREAMING_SNAKE_CASE_ )
										snake_case__    :   Optional[int]							     =   self._Node(SCREAMING_SNAKE_CASE_ ,SCREAMING_SNAKE_CASE_ ,SCREAMING_SNAKE_CASE_ )
										snake_case__    :   Union[str, Any]							     =   self._trailer
										snake_case__    :   Union[str, Any]							     =   self._header
										snake_case__    :   Any							     =   0

				def __len__(				self				:       str ):
										return self._size

				def  _lowerCamelCase   (				self				:       Union[str, Any] ):
										return self.__len__() == 0

				def  _lowerCamelCase   (				self				:       Any ,SCREAMING_SNAKE_CASE_				:       List[Any] ,SCREAMING_SNAKE_CASE_				:       List[str] ,SCREAMING_SNAKE_CASE_				:       Dict ):
										# Create new_node by setting it's prev.link -> header
										# setting it's next.link -> trailer
										snake_case__    :   Dict							     =   self._Node(SCREAMING_SNAKE_CASE_ ,SCREAMING_SNAKE_CASE_ ,SCREAMING_SNAKE_CASE_ )
										snake_case__    :   Any							     =   new_node
										snake_case__    :   str							     =   new_node
										self._size += 1
										return self





				def  _lowerCamelCase   (				self				:       Union[str, Any] ,SCREAMING_SNAKE_CASE_				:       Dict ):
										snake_case__    :   Union[str, Any]							     =   node._prev
										snake_case__    :   Union[str, Any]							     =   node._next

										snake_case__    :   List[Any]							     =   successor
										snake_case__    :   Dict							     =   predecessor
										self._size -= 1
										snake_case__    :   Dict							     =   node._data
										snake_case__    :   List[str]							     =   None
										del node
										return temp







class  __lowercase    (     _DoublyLinkedBase		):


				'''simple docstring'''


				def  _lowerCamelCase   (				self				:       Optional[int] ):
										if self.is_empty():
																raise Exception('''List is empty''' )
										return self._header._next._data

				def  _lowerCamelCase   (				self				:       Union[str, Any] ):
										if self.is_empty():
																raise Exception('''List is empty''' )
										return self._trailer._prev._data

				def  _lowerCamelCase   (				self				:       Any ,SCREAMING_SNAKE_CASE_				:       Dict ):
										return self._insert(self._header ,SCREAMING_SNAKE_CASE_ ,self._header._next )

				def  _lowerCamelCase   (				self				:       Dict ,SCREAMING_SNAKE_CASE_				:       Union[str, Any] ):
										return self._insert(self._trailer._prev ,SCREAMING_SNAKE_CASE_ ,self._trailer )

				def  _lowerCamelCase   (				self				:       Optional[int] ):
										if self.is_empty():
																raise IndexError('''remove_first from empty list''' )
										return self._delete(self._header._next )





				def  _lowerCamelCase   (				self				:       Optional[Any] ):
										if self.is_empty():
																raise IndexError('''remove_first from empty list''' )
										return self._delete(self._trailer._prev )


