





import math
from collections.abc import Generator






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






def  SCREAMING_SNAKE_CASE__							(				UpperCamelCase__:							int			):
		SCREAMING_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):
				SCREAMING_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  SCREAMING_SNAKE_CASE__							(				):
		from timeit import timeit

		SCREAMING_SNAKE_CASE__								=					"""from __main__ import slow_primes, primes, fast_primes"""
		print(timeit("""slow_primes(1_000_000_000_000)"""    ,      setup=UpperCamelCase__    ,      number=1_000_000			)			)
		print(timeit("""primes(1_000_000_000_000)"""    ,      setup=UpperCamelCase__    ,      number=1_000_000			)			)
		print(timeit("""fast_primes(1_000_000_000_000)"""    ,      setup=UpperCamelCase__    ,      number=1_000_000			)			)


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






from __future__ import annotations

from collections import deque
from queue import Queue
from timeit import timeit

_lowerCamelCase       =	{
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E'],
}






def  SCREAMING_SNAKE_CASE__							(				UpperCamelCase__:							dict    ,      UpperCamelCase__:							str			):
		SCREAMING_SNAKE_CASE__								=					{start}
		SCREAMING_SNAKE_CASE__								=					[start]
		SCREAMING_SNAKE_CASE__								=					Queue()
		queue.put(UpperCamelCase__			)
		while not queue.empty():
				SCREAMING_SNAKE_CASE__								=					queue.get()
				for w in graph[v]:
						if w not in explored:
								explored.add(UpperCamelCase__			)
								result.append(UpperCamelCase__			)
								queue.put(UpperCamelCase__			)
		return result






def  SCREAMING_SNAKE_CASE__							(				UpperCamelCase__:							dict    ,      UpperCamelCase__:							str			):
		SCREAMING_SNAKE_CASE__								=					{start}
		SCREAMING_SNAKE_CASE__								=					[start]
		SCREAMING_SNAKE_CASE__								=					deque([start]			)
		while queue:
				SCREAMING_SNAKE_CASE__								=					queue.popleft()
				for child in graph[v]:
						if child not in visited:
								visited.add(UpperCamelCase__			)
								result.append(UpperCamelCase__			)
								queue.append(UpperCamelCase__			)
		return result






def  SCREAMING_SNAKE_CASE__							(				UpperCamelCase__:							str			):
		SCREAMING_SNAKE_CASE__								=					f'''from __main__ import G, {name}'''
		SCREAMING_SNAKE_CASE__								=					10_000
		SCREAMING_SNAKE_CASE__								=					timeit(f'''{name}(G, \'A\')'''    ,      setup=UpperCamelCase__    ,      number=UpperCamelCase__			)
		print(f'''{name:<35} finished {number} runs in {res:.5f} seconds'''			)


if __name__ == "__main__":
	import doctest

	doctest.testmod()

	benchmark_function('breadth_first_search')
	benchmark_function('breadth_first_search_with_deque')
	# breadth_first_search                finished 10000 runs in 0.20999 seconds
	# breadth_first_search_with_deque     finished 10000 runs in 0.01421 seconds