



from __future__ import annotations

from functools import lru_cache
from math import ceil

UpperCAmelCase__       =	100

UpperCAmelCase__       =	set(range(3, NUM_PRIMES, 2))
primes.add(2)
UpperCAmelCase__       =	42

for prime in range(3, ceil(NUM_PRIMES**0.5), 2):
       if prime not in primes:
              continue
       primes.difference_update(set(range(prime * prime, NUM_PRIMES, prime)))





@lru_cache(maxsize=100   )
def 							A     (					_UpperCAmelCase    :       int   )    ->			str:







   '''simple docstring'''
   if number_to_partition < 0:
      return set()
   elif number_to_partition == 0:
      return {1}

   _UpperCAmelCase			=       set()
   _UpperCAmelCase			=       42
   _UpperCAmelCase			=       42

   for prime in primes:
      if prime > number_to_partition:
         continue
      for sub in partition(number_to_partition - prime   ):
         ret.add(sub * prime   )

   return ret





def 							A     (					_UpperCAmelCase    :       int = 5_000   )    ->			List[str]:







   '''simple docstring'''
   for number_to_partition in range(1							,       _UpperCAmelCase   ):
      if len(partition(_UpperCAmelCase   )   ) > number_unique_partitions:
         return number_to_partition
   return None


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





from __future__ import annotations

from itertools import permutations
from random import randint
from timeit import repeat





def 							A     (					)    ->			tuple[list[int], int]:







			'''simple docstring'''
			_UpperCAmelCase			=       [randint(-1_000							,       1_000   ) for i in range(10   )]
			_UpperCAmelCase			=       randint(-5_000							,       5_000   )
			return (arr, r)


UpperCAmelCase__       =	make_dataset()





def 							A     (					_UpperCAmelCase    :       list[int]							,       _UpperCAmelCase    :       int   )    ->			tuple[int, ...]:







			'''simple docstring'''
			for triplet in permutations(_UpperCAmelCase							,       3   ):
						if sum(_UpperCAmelCase   ) == target:
									return tuple(sorted(_UpperCAmelCase   )   )
			return (0, 0, 0)





def 							A     (					_UpperCAmelCase    :       list[int]							,       _UpperCAmelCase    :       int   )    ->			tuple[int, int, int]:







			'''simple docstring'''
			arr.sort()
			_UpperCAmelCase			=       len(_UpperCAmelCase   )
			for i in range(n - 1   ):
						_UpperCAmelCase	,					_UpperCAmelCase			=       i + 1, n - 1
						while left < right:
									if arr[i] + arr[left] + arr[right] == target:
												return (arr[i], arr[left], arr[right])
									elif arr[i] + arr[left] + arr[right] < target:
												left += 1
									elif arr[i] + arr[left] + arr[right] > target:
												right -= 1
			return (0, 0, 0)





def 							A     (					)    ->			tuple[float, float]:







			'''simple docstring'''
			_UpperCAmelCase			=       '\nfrom __main__ import dataset, triplet_sum1, triplet_sum2\n'
			_UpperCAmelCase			=       '\ntriplet_sum1(*dataset)\n'
			_UpperCAmelCase			=       '\ntriplet_sum2(*dataset)\n'
			_UpperCAmelCase			=       repeat(setup=_UpperCAmelCase							,       stmt=_UpperCAmelCase							,       repeat=5							,       number=10_000   )
			_UpperCAmelCase			=       repeat(setup=_UpperCAmelCase							,       stmt=_UpperCAmelCase							,       repeat=5							,       number=10_000   )
			return (min(_UpperCAmelCase   ), min(_UpperCAmelCase   ))


if __name__ == "__main__":
							from doctest import testmod

							testmod()
							UpperCAmelCase__       =	solution_times()
							print(f"""The time for naive implementation is {times[0]}.""")
							print(f"""The time for optimized implementation is {times[1]}.""")
