




def 						lowerCamelCase__    (		_A     ,	_A     ,	_A							):







	'''simple docstring'''





	def update_area_of_max_square(_A     ,	_A							) -> int:
		# BASE CASE
		if row >= rows or col >= cols:
			return 0

		snake_case_		    =     update_area_of_max_square(_A     ,	col + 1							)
		snake_case_		    =     update_area_of_max_square(row + 1     ,	col + 1							)
		snake_case_		    =     update_area_of_max_square(row + 1     ,	_A							)

		if mat[row][col]:
			snake_case_		    =     1 + min([right, diagonal, down]							)
			snake_case_		    =     max(largest_square_area[0]     ,	_A							)
			return sub_problem_sol
		else:
			return 0

	snake_case_		    =     [0]
	update_area_of_max_square(0     ,	0							)
	return largest_square_area[0]


def 						lowerCamelCase__    (		_A     ,	_A     ,	_A							):







	'''simple docstring'''





	def update_area_of_max_square_using_dp_array(
	    _A     ,	_A     ,	_A							) -> int:
		if row >= rows or col >= cols:
			return 0
		if dp_array[row][col] != -1:
			return dp_array[row][col]

		snake_case_		    =     update_area_of_max_square_using_dp_array(_A     ,	col + 1     ,	_A							)
		snake_case_		    =     update_area_of_max_square_using_dp_array(row + 1     ,	col + 1     ,	_A							)
		snake_case_		    =     update_area_of_max_square_using_dp_array(row + 1     ,	_A     ,	_A							)

		if mat[row][col]:
			snake_case_		    =     1 + min([right, diagonal, down]							)
			snake_case_		    =     max(largest_square_area[0]     ,	_A							)
			snake_case_		    =     sub_problem_sol
			return sub_problem_sol
		else:
			return 0

	snake_case_		    =     [0]
	snake_case_		    =     [[-1] * cols for _ in range(_A							)]
	update_area_of_max_square_using_dp_array(0     ,	0     ,	_A							)

	return largest_square_area[0]


def 						lowerCamelCase__    (		_A     ,	_A     ,	_A							):







	'''simple docstring'''





	snake_case_		    =     [[0] * (cols + 1) for _ in range(rows + 1							)]
	snake_case_		    =     0
	for row in range(rows - 1     ,	-1     ,	-1							):
		for col in range(cols - 1     ,	-1     ,	-1							):
			snake_case_		    =     dp_array[row][col + 1]
			snake_case_		    =     dp_array[row + 1][col + 1]
			snake_case_		    =     dp_array[row + 1][col]

			if mat[row][col] == 1:
				snake_case_		    =     1 + min(_A     ,	_A     ,	_A							)
				snake_case_		    =     max(dp_array[row][col]     ,	_A							)
			else:
				snake_case_		    =     0

	return largest_square_area


def 						lowerCamelCase__    (		_A     ,	_A     ,	_A							):







	'''simple docstring'''





	snake_case_		    =     [0] * (cols + 1)
	snake_case_		    =     [0] * (cols + 1)
	snake_case_		    =     0
	for row in range(rows - 1     ,	-1     ,	-1							):
		for col in range(cols - 1     ,	-1     ,	-1							):
			snake_case_		    =     current_row[col + 1]
			snake_case_		    =     next_row[col + 1]
			snake_case_		    =     next_row[col]

			if mat[row][col] == 1:
				snake_case_		    =     1 + min(_A     ,	_A     ,	_A							)
				snake_case_		    =     max(current_row[col]     ,	_A							)
			else:
				snake_case_		    =     0
		snake_case_		    =     current_row

	return largest_square_area


if __name__ == "__main__":
		import doctest

		doctest.testmod()
		print(largest_square_area_in_matrix_bottom_up(2, 2, [[1, 1], [1, 1]]))






def 						lowerCamelCase__    (		_A							):







	'''simple docstring'''





	if num <= 0:
		raise ValueError("Input must be a positive integer"							)

	snake_case_		    =     [True] * (num + 1)

	snake_case_		    =     2
	while p * p <= num:
		if primes[p]:
			for i in range(p * p     ,	num + 1     ,	_A							):
				snake_case_		    =     False
		p += 1

	return [prime for prime in range(2     ,	num + 1							) if primes[prime]]


if __name__ == "__main__":
		import doctest

		doctest.testmod()

		lowercase__				:     Tuple 		=						int(input("Enter a positive integer: ").strip())
		print(prime_sieve_eratosthenes(user_num))
