




"""simple docstring"""
from __future__ import annotations

import math





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

			if num <= 0:
						__lowerCamelCase					:	Optional[int]	       =				f'''{num}: Invalid input, please enter a positive integer.'''
						raise ValueError(A__     )

			__lowerCamelCase					:	Union[str, Any]	       =				[True] * (num + 1)
			__lowerCamelCase					:	int	       =				[]
			__lowerCamelCase					:	Optional[int]	       =				2
			__lowerCamelCase					:	Optional[int]	       =				int(math.sqrt(A__     )     )

			while start <= end:
						# If start is a prime
						if sieve[start] is True:
									prime.append(A__     )

									# Set multiples of start be False
									for i in range(start * start							,				num + 1							,				A__     ):
												if sieve[i] is True:
															__lowerCamelCase					:	Any	       =				False

						start += 1

			for j in range(end + 1							,				num + 1     ):
						if sieve[j] is True:
									prime.append(A__     )

			return prime


if __name__ == "__main__":
					print(prime_sieve(int(input('''Enter a positive integer: ''').strip())))









"""simple docstring"""
import random





def 						UpperCAmelCase				(			A__:    Union[str, Any]							,				A__:    List[str]							,				A__:    Union[str, Any]     )  ->     int:
			__lowerCamelCase					:	Optional[Any]	       =				a[left_index]
			__lowerCamelCase					:	int	       =				left_index + 1
			for j in range(left_index + 1							,				A__     ):
						if a[j] < pivot:
									__lowerCamelCase       ,      __lowerCamelCase					:	Optional[int]	       =				a[i], a[j]
									i += 1
			__lowerCamelCase       ,      __lowerCamelCase					:	str	       =				a[i - 1], a[left_index]
			return i - 1





def 						UpperCAmelCase				(			A__:    List[Any]							,				A__:    Tuple							,				A__:    Tuple     )  ->     Dict:
			if left < right:
						__lowerCamelCase					:	Optional[int]	       =				random.randint(A__							,				right - 1     )
						__lowerCamelCase       ,      __lowerCamelCase					:	int	       =				(
						    a[left],
						    a[pivot],
						)  # switches the pivot with the left most bound
						__lowerCamelCase					:	Union[str, Any]	       =				partition(A__							,				A__							,				A__     )
						quick_sort_random(
						    A__							,				A__							,				A__     )  # recursive quicksort to the left of the pivot point
						quick_sort_random(
						    A__							,				pivot_index + 1							,				A__     )  # recursive quicksort to the right of the pivot point





def 						UpperCAmelCase				(			)  ->     int:
			__lowerCamelCase					:	Dict	       =				input('Enter numbers separated by a comma:\n'     ).strip()
			__lowerCamelCase					:	int	       =				[int(A__     ) for item in user_input.split(','     )]

			quick_sort_random(A__							,				0							,				len(A__     )     )

			print(A__     )


if __name__ == "__main__":
					main()



