




"""simple docstring"""
import math





def 						UpperCAmelCase				(			A__:    int     )  ->     list[int]:
			__lowerCamelCase					:	Optional[Any]	       =				[]
			__lowerCamelCase					:	Optional[int]	       =				2
			__lowerCamelCase					:	Tuple	       =				int(math.sqrt(A__     )     )  # Size of every segment
			__lowerCamelCase					:	Optional[Any]	       =				[True] * (end + 1)
			__lowerCamelCase					:	Tuple	       =				[]

			while start <= end:
						if temp[start] is True:
									in_prime.append(A__     )
									for i in range(start * start							,				end + 1							,				A__     ):
												__lowerCamelCase					:	Tuple	       =				False
						start += 1
			prime += in_prime

			__lowerCamelCase					:	Optional[Any]	       =				end + 1
			__lowerCamelCase					:	int	       =				min(2 * end							,				A__     )

			while low <= n:
						__lowerCamelCase					:	List[str]	       =				[True] * (high - low + 1)
						for each in in_prime:
									__lowerCamelCase					:	Union[str, Any]	       =				math.floor(low / each     ) * each
									if t < low:
												t += each

									for j in range(A__							,				high + 1							,				A__     ):
												__lowerCamelCase					:	int	       =				False

						for j in range(len(A__     )     ):
									if temp[j] is True:
												prime.append(j + low     )

						__lowerCamelCase					:	str	       =				high + 1
						__lowerCamelCase					:	Tuple	       =				min(high + end							,				A__     )

			return prime






print(sieve(10**6))









"""simple docstring"""
def 						UpperCAmelCase				(			A__:    int							,				A__:    list[int]							,				A__:    int     )  ->     int:

			def count_of_possible_combinations(A__:    int     ) -> int:
						if target < 0:
									return 0
						if target == 0:
									return 1
						return sum(count_of_possible_combinations(target - item     ) for item in array     )

			return count_of_possible_combinations(A__     )





def 						UpperCAmelCase				(			A__:    int							,				A__:    list[int]							,				A__:    int     )  ->     int:

			def count_of_possible_combinations_with_dp_array(
			    A__:    int							,				A__:    list[int]     ) -> int:
						if target < 0:
									return 0
						if target == 0:
									return 1
						if dp_array[target] != -1:
									return dp_array[target]
						__lowerCamelCase					:	Dict	       =				sum(
						    count_of_possible_combinations_with_dp_array(target - item							,				A__     )
						    for item in array     )
						__lowerCamelCase					:	str	       =				answer
						return answer

			__lowerCamelCase					:	Union[str, Any]	       =				[-1] * (target + 1)
			return count_of_possible_combinations_with_dp_array(A__							,				A__     )





def 						UpperCAmelCase				(			A__:    int							,				A__:    list[int]							,				A__:    int     )  ->     int:
			__lowerCamelCase					:	int	       =				[0] * (target + 1)
			__lowerCamelCase					:	str	       =				1

			for i in range(1							,				target + 1     ):
						for j in range(A__     ):
									if i - array[j] >= 0:
												dp_array[i] += dp_array[i - array[j]]

			return dp_array[target]


if __name__ == "__main__":
					import doctest

					doctest.testmod()
					a_				:    Any										=     3
					a_				:    str										=     5
					a_				:    List[Any]										=     [1, 2, 5]
					print(combination_sum_iv(n, array, target))



