c++ - 验证输出以“查找 1 到 1000 之间的数，其质因数之和本身就是质数”来自 Alllain 的 Jumping into C++ (ch7 #3)

Question

问题：

设计一个程序，找出从 1 到 1000 的所有数，其质因数相加时总和为质数（例如，12 的质因数为 2、2 和 3，总和为 7，即质数） . 实现该算法的代码。

我将问题修改为仅对唯一因子求和，因为我不明白为什么您要计算一个因子两次，就像他使用 12 的示例一样。

我的解决方案。有什么好的（阅读：自动化）方法来验证我的程序的输出吗？

1 到 1000 的样本输出：

更新：我已经解决了我的问题并使用OEIS 给定系列验证了我的程序的输出，正如@MVW 所建议的那样（在我的新 github 解决方案给出的源代码中显示）。将来，我的目标是通过执行以下零个或多个（取决于问题的范围/重要性）来测试我的程序：

谷歌关键字找到问题的现有解决方案，如果我找到它，将其与我的解决方案进行比较
单元测试组件在构建和集成时的正确性，将这些测试与已知的正确输出进行比较

score 1 · Accepted Answer

一些建议：

您需要检查计算出的数字的属性。这意味着

计算主要因素和
计算它们的总和和
测试该总和是否为质数。

顺便说一句，这是您的程序首先应该做的事情。

因此，检查的一个不错的选择是将您的输出与已知解决方案或已知可以工作的另一个程序的输出进行比较。棘手的一点是有这样的解决方案或程序可用。而且我忽略了您的比较也可能受到错误的困扰:-)

如果你只是将它与其他实现进行比较，例如这里其他人的程序，它会变成更多的投票，它不会是一个证明。如果几个独立的实现得出相同的结果，它只会增加您的程序正确的可能性。当然，所有实现都可能出错:-) 越同意越好。实现越多样化越好。例如，您可以使用不同的编程语言、代数系统或有时间、纸笔和维基百科的朋友。:-)

另一种方法是在中间步骤中添加检查，以使您对结果更有信心。一种建立信任链的方式。

您可以输出您确定的素因子，并将其与已知有效的素因子分解程序的输出进行比较。
然后你检查你的求和是否有效。
最后，您可以通过输入已知素数和非素数等来检查您应用于候选总和的素数测试是否正常工作。

例如，这就是人们对单元测试所做的事情。试图覆盖代码的大部分工作，希望如果部分工作，整个工作。

或者您可以逐步正式地证明您的程序，例如使用 Hoare Calculus或其他形式方法。但这很棘手，您最终可能会将程序错误转变为证明中的错误。

而今天，在互联网时代，你当然可以上网搜索解决方案：

尝试在整数序列在线百科全书中搜索素数之和是素数，这应该会为您提供系列A100118。:-) 这是多重性的问题，但向您展示了数论专业人士所做的事情，使用 Mathematica 和程序片段来计算级数、案例 1 的论证和文献。相当令人印象深刻。

score 1 · Accepted Answer

这是我得到的答案。我排除了 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)]

您可以硬编码此列表并对其进行测试。我非常有信心这些结果没有错误。

（读.为“的”）。

c++ - 验证输出以“查找 1 到 1000 之间的数，其质因数之和本身就是质数”来自 Alllain 的 Jumping into C++ (ch7 #3)

2 回答 2

Related

Reference