



'''simple docstring'''

def 				a  (     UpperCamelCase_    :    int = 1000000			)       ->	int:
		snake_case__	     =set(range(3      ,					UpperCamelCase_      ,					2			)			)
		primes.add(2			)
		for p in range(3      ,					UpperCamelCase_      ,					2			):
				if p not in primes:
						continue
				primes.difference_update(set(range(p * p      ,					UpperCamelCase_      ,					UpperCamelCase_			)			)			)

		snake_case__	     =[float(UpperCamelCase_			) for n in range(limit + 1			)]

		for p in primes:
				for n in range(UpperCamelCase_      ,					limit + 1      ,					UpperCamelCase_			):
						phi[n] *= 1 - 1 / p

		return int(sum(phi[2:]			)			)


if __name__ == "__main__":
			print(f"""{solution() = }""")









'''simple docstring'''

from __future__ import annotations






def 				a  (     UpperCamelCase_    :    list[int]      ,					UpperCamelCase_    :    list[int]      ,					UpperCamelCase_    :    int			)       ->	tuple[float, list[float]]:
		snake_case__	     =list(range(len(UpperCamelCase_			)			)			)
		snake_case__	     =[v / w for v, w in zip(UpperCamelCase_      ,					UpperCamelCase_			)]
		index.sort(key=lambda UpperCamelCase_			: ratio[i]      ,					reverse=UpperCamelCase_			)

		snake_case__	     =0
		snake_case__	     =[0] * len(UpperCamelCase_			)
		for i in index:
				if weight[i] <= capacity:
						snake_case__	     =1
						max_value += value[i]
						capacity -= weight[i]
				else:
						snake_case__	     =capacity / weight[i]
						max_value += value[i] * capacity / weight[i]
						break

		return max_value, fractions


if __name__ == "__main__":
			import doctest

			doctest.testmod()




