





from __future__ import annotations

from queue import Queue





class   lowercase__     :







  def __init__(						self    ):
       lowerCAmelCase_       :							Any			 =		{}







  def 						UpperCAmelCase__		(						self    ):

       for i in self.vertices:
            print(_lowercase     ,    """ : """     ,    """ -> """.join([str(_lowercase    ) for j in self.vertices[i]]    )    )







  def 						UpperCAmelCase__		(						self     ,    _lowercase     ,    _lowercase    ):

       if from_vertex in self.vertices:
            self.vertices[from_vertex].append(_lowercase    )
       else:
            lowerCAmelCase_       :							List[Any]			 =		[to_vertex]







  def 						UpperCAmelCase__		(						self     ,    _lowercase    ):
       lowerCAmelCase_       :							str			 =		set()

       # create a first in first out queue to store all the vertices for BFS
       lowerCAmelCase_       :							str			 =		Queue()

       # mark the source node as visited and enqueue it
       visited.add(_lowercase    )
       queue.put(_lowercase    )

       while not queue.empty():
            lowerCAmelCase_       :							int			 =		queue.get()

            # loop through all adjacent vertex and enqueue it if not yet visited
            for adjacent_vertex in self.vertices[vertex]:
                 if adjacent_vertex not in visited:
                      queue.put(_lowercase    )
                      visited.add(_lowercase    )
       return visited


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

      testmod(verbose=True)

      UpperCAmelCase_       : List[str]							=    Graph()
      g.add_edge(0, 1)
      g.add_edge(0, 2)
      g.add_edge(1, 2)
      g.add_edge(2, 0)
      g.add_edge(2, 3)
      g.add_edge(3, 3)

      g.print_graph()
      # 0  :  1 -> 2
      # 1  :  2
      # 2  :  0 -> 3
      # 3  :  3

      assert sorted(g.bfs(2)) == [0, 1, 2, 3]

"""simple docstring"""
import math
from collections.abc import Generator





def  lowerCAmelCase__     (      _UpperCamelCase							:					int       )       ->					Generator[int, None, None]:





						"""simple docstring"""






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





def  lowerCAmelCase__     (      _UpperCamelCase							:					int       )       ->					Generator[int, None, None]:





						"""simple docstring"""






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





def  lowerCAmelCase__     (      _UpperCamelCase							:					int       )       ->					Generator[int, None, None]:





						"""simple docstring"""






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





def  lowerCAmelCase__     (      )       ->					List[str]:





						"""simple docstring"""






						from timeit import timeit

						snake_case             =      'from __main__ import slow_primes, primes, fast_primes'
						print(timeit('slow_primes(1_000_000_000_000)'			,      setup=_UpperCamelCase			,      number=1_0_0_0_0_0_0       )       )
						print(timeit('primes(1_000_000_000_000)'			,      setup=_UpperCamelCase			,      number=1_0_0_0_0_0_0       )       )
						print(timeit('fast_primes(1_000_000_000_000)'			,      setup=_UpperCamelCase			,      number=1_0_0_0_0_0_0       )       )


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


