Короче говоря : максимальное число простых чисел для числа составляет 3. Поскольку существует только 168 простых чисел, меньших 1000, мы можем исчерпывающе использовать комбинацию двух простых чисел или значение по умолчанию 3. Используя некоторые дополнительные свойства, мы можем легко определить минимальное количество элементов и даже создать коллекцию. из этих чисел.
Мы можем решить эту проблему, если предположим, что у нас есть доступ к списку простых чисел до 1000, из них 168.
Учитывая, что число является простым числом, тогда, очевидно, ответ будет 1 .
Для не простых чисел нам придется искать разные способы решения проблемы.
гипотеза Гольдбаха [wiki] утверждает, что
Каждое четное целое число больше 2 можно выразить как сумму двух простых чисел .
Эта гипотеза не проверена в целом, но, по крайней мере, известно, что она справедлива для всех чисел до 4 & times; 10 18 .
Таким образом, это означает, что для n = 2 ответ - 1, а для даже n > 2 - 2 (поскольку существует только одно четное простое число).
Если число нечетное и не простое, мы знаем, что максимальное число простых чисел равно 3. Действительно, поскольку, если мы вычтем 3 из этого числа, мы получим четное число, которое может быть составлено из 2 или трех элементов. По-видимому, это известно как предельная гипотеза Гольдбаха [wiki] :
Каждое целое число больше 5 можно записать как сумму трех простых чисел.
Единственный способ улучшить верхнюю границу - это найти два простых чисел, которые суммируют до заданного числа. Таким образом, для этого требуется выполнить итерацию по всем простым числам (не более 1 000) и проверить, есть ли также, если n - p также простое число. Однако, как говорит @ AlexanderZhang , мы можем просто вычесть 2, поскольку это единственное четное число, которое приведет к нечетному числу и, следовательно, является кандидатом на простое число.
Итак, подведем итог: в основном есть следующие случаи:
- для n <2 </em>, простых чисел нет, поэтому, очевидно, происходит сбой;
- для n простого числа, ответ, конечно, один, так как мы можем просто использовать это число;
- для четных чисел, больших двух, мы можем использовать гипотезу Гольдбаха и, таким образом, вернуть
2, мы знаем, что это минимально, поскольку, кроме 2, четных чисел нет;
- для нечетных чисел, больших двух, мы знаем, что если n-2 простое, то число равно 2, поскольку
2 - простое число, а n-2 - простое число, мы знаем, что лучшего решения не существует, поскольку n не является простым; и наконец
- для нечетного числа, где n-2 не является простым, мы знаем, что n-3 равно даже , и согласно предположению Гольдбаха, мы можем построить сумма трех простых чисел. Мы знаем, что это оптимально, поскольку без простого числа, отличного от
2, вычитание является четным, и, следовательно, мы снова можем использовать гипотезу Гольдбаха.
Таким образом, мы можем реализовать алгоритм вроде:
primes1000 = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997}
def min_prime(n):
if n < 2:
return -1
if n in primes1000:
return 1
# 2 and 3 are prime numbers prime number
# so all values here are > 3
if n % 2 == 0:
return 2 # Goldbach's conjecture, so 2
if n-2 in primes1000:
return 2
return 3 # fallback on 3
Например:
>>> min_prime(12)
2
>>> min_prime(14)
2
>>> min_prime(88)
2
>>> min_prime(117)
3
>>> min_prime(374)
2
>>> min_prime(363)
3
>>> min_prime(11)
1
Генерация простых чисел
Мы можем использовать тот же подход для генерации простых чисел, например:
def find_sum2(n):
for p in primes1000:
if n-p in primes1000:
return (p, n-p)
def min_prime_tuple(n):
if n < 2:
return None
if n in primes1000:
return (n,)
if n % 2 == 0:
return find_sum2(n)
if n-2 in primes1000:
return (2, n-2)
return (3, *find_sum2(n-3))
Например:
>>> min_prime_tuple(12)
(5, 7)
>>> min_prime_tuple(14)
(3, 11)
>>> min_prime_tuple(88)
(5, 83)
>>> min_prime_tuple(117)
(3, 5, 109)
>>> min_prime_tuple(374)
(7, 367)
>>> min_prime_tuple(363)
(3, 7, 353)
>>> min_prime_tuple(11)
(11,)
Мы можем улучшить вышесказанное с точки зрения эффективности, отключив линейный поиск с того момента, когда итератор больше, чем n, но обычно это не будет иметь большого значения, так как число простых чисел меньше 1000 равно совсем маленький.
Performance
Так как n имеет верхнюю границу 1'000, биг-ой нет. Более того, если n не ограничено, мы не знаем, остается ли гипотеза верной.
Если предположить, что гипотеза верна, то генерация кортежа выполняется за O (g × c) с g временем генерации всех простых чисел до n и c время, чтобы проверить, является ли число простым числом.
Если мы сравниваем вышеупомянутый не очень эффективно реализованный подход в Python, мы достигаем следующего теста:
>>> timeit(lambda: list(map(min_prime_tuple, range(0,1000))), number=10_000)
4.081021320000218
Таким образом, это означает, что если мы 10 000 раз построим кортежи для всех чисел до 1 000, то это будет сделано за 4,08 секунды на Intel (R) Core (TM) i7-7500U CPU @ 2,70 ГГц .Таким образом, это означает, что мы можем проверить весь диапазон за 408,1 мкс или случайное число приблизительно за 0,408 мкс.