алгоритм — проверка выходных данных на «Поиск чисел от 1 до 1000, сумма простых множителей которых сама по себе является простым числом»; из «Прыжка Аллена в C ++» (глава 7)

Question

алгоритм — проверка выходных данных на «Поиск чисел от 1 до 1000, сумма простых множителей которых сама по себе является простым числом»; из «Прыжка Аллена в C ++» (глава 7)

Вопрос:

Разработайте программу, которая находит все числа от 1 до 1000, чьи основные факторы при добавлении
вместе суммируем до простого числа (например, 12 имеет простые множители 2, 2 и 3, которые
сумма до 7, что является простым). Реализуйте код для этого алгоритма.

Я изменил задачу, чтобы суммировать только уникальные факторы, потому что я не понимаю, почему вы учитываете фактор дважды, как в его примере с использованием 12.

Мое решение. Есть ли какой-нибудь хороший (читай: автоматизированный) способ проверить вывод моей программы?

Пример вывода от 1 до 1000:

Обновить: Я решил свою проблему и проверил вывод моей программы, используя OEIS данная серия, как предложено @MVW (показано в источнике, предоставленном мое новое решение GitHub). В будущем я буду стремиться протестировать свои программы, выполнив ноль или более следующих действий (в зависимости от масштаба / важности проблемы):

Google ключевые слова для существующего решения проблемы, сравнивая его с моим решением, если я найду его
Компоненты модульного теста на правильность, как они построены и интегрированы, сравнивая эти тесты с известными правильными результатами

0

algorithm automation c++oeis testing

Решение

Другие решения

Вот ответ, который я получаю. Я исключаю 1, поскольку у него нет простых делителей, поэтому их сумма равна 0, а не простому числу.

Haskell> filter (isPrime . sum . map fst . primePowers) [2..1000]
[2,3,4,5,6,7,8,9,10,11,12,13,16,17,18,19,20,22,23,24,25,27,29,31,32,34,36,37,40,
41,43,44,47,48,49,50,53,54,58,59,61,64,67,68,71,72,73,79,80,81,82,83,88,89,96,97
,100,101,103,107,108,109,113,116,118,121,125,127,128,131,136,137,139,142,144,149
,151,157,160,162,163,164,165,167,169,173,176,179,181,191,192,193,197,199,200,202
,210,211,214,216,223,227,229,232,233,236,239,241,242,243,250,251,256,257,263,269
,271,272,273,274,277,281,283,284,288,289,293,298,307,311,313,317,320,324,328,331
,337,343,345,347,349,352,353,358,359,361,367,373,379,382,383,384,385,389,390,394
,397,399,400,401,404,409,419,420,421,428,431,432,433,435,439,443,449,454,457,461
,462,463,464,467,472,478,479,484,486,487,491,495,499,500,503,509,512,521,523,529
,538,541,544,547,548,557,561,562,563,568,569,570,571,576,577,578,587,593,595,596
,599,601,607,613,617,619,622,625,630,631,640,641,643,647,648,651,653,656,659,661
,665,673,677,683,691,694,701,704,709,714,715,716,719,727,729,733,739,743,751,757
,759,761,764,768,769,773,777,780,787,788,795,797,798,800,808,809,811,819,821,823
,825,827,829,838,839,840,841,853,856,857,858,859,862,863,864,877,881,883,885,887
,903,907,908,911,919,922,924,928,929,930,937,941,944,947,953,956,957,961,967,968
,971,972,977,983,991,997,1000]

Haskell> primePowers 12
[(2,2),(3,1)]

Haskell> primePowers 14
[(2,1),(7,1)]

Вы можете жестко закодировать этот список и проверить его. Я уверен, что эти результаты без ошибок.

(читать . имеет»).

1

Источник

Accepted Answer

Некоторые предложения:

Вам необходимо проверить свойства ваших рассчитанных чисел.
Вот что значит

расчет основных факторов и
рассчитывая их сумму и
проверка, является ли эта сумма простым числом.

Кстати, именно это и должна делать ваша программа.

Итак, один хороший вариант для проверки сравнивая ваш вывод с известным решением или выводом другой программы, которая, как известно, работает. Хитрость в том, чтобы иметь такое решение или программу доступной. И я пренебрегаю тем, что ваше сравнение может быть также изведено ошибками 🙂

Если вы просто сравнить это с другими реализациями, например Программы от других людей здесь, это будет больше голосования, это не будет доказательством. Это просто увеличит вероятность того, что ваша программа верна, если несколько независимых реализаций получат одинаковый результат. Конечно, все реализации могут ошибаться 🙂
Чем больше согласен, тем лучше.
А также чем разнообразнее реализации, тем лучше.
Например. Вы могли бы использовать разные языки программирования, алгебраические системы или друга с временем и бумагой и карандашом и Википедия. 🙂

Другим средством является добавить проверки к вашим промежуточным шагам, чтобы получить больше уверенности в своем результате. Вид построения цепочки доверия.

Вы можете вывести основные факторы, которые вы определили, и сравнить их с результатами.
основной программы факторизации, которая, как известно, работает.
Затем вы проверяете, работает ли ваше суммирование.
Наконец, вы можете проверить, правильно ли работает тест на простоту, который вы применяете к суммам кандидатов, добавив в него известные простые числа и не простые числа и так далее.

Это то, что люди делают с модульное тестирование например. Попытка охватить большинство частей кода как работающие, надеясь, что эти части работают, что все будет работать.

Или ты мог официально доказать свою программу шаг за шагом, используя Исчисление Хоара например или другой формальный метод.
Но это сложно, и вы можете в конечном итоге перевести программные ошибки на ошибки в доказательстве.

И сегодня, в эпоху интернета, можно поиск решения в интернете:

Пытаться в поисках сумма простых факторов проста в онлайн-энциклопедии целочисленных последовательностей, который должен дать вам серию A100118. 🙂
Это проблема множественности, но она показывает вам, что делают профессионалы теории чисел, с Mathematica и фрагментами программы для вычисления ряда, аргумент для случая 1 и литература. Довольно впечатляющий.

1