Verifying output to "Find the numbers between 1 and 1000 whose prime factors' sum is itself a prime" from Allain's Jumping into C++ (ch7 #3)

Question 1

Some suggestions:

You need to check the properties of your calculated numbers. Here that means

calculating the prime factors and
calculating their sum and
testing if that sum is a prime number.

Which is what your program should do in the first place, by the way.

So one nice option for checking is comparing your output with a known solution or the output of a another program which is known to work. The tricky bit is to have such a solution or program available. And I neglect that your comparison could be plagued by errors as well :-)

If you just compare it with other implementations, e.g. programs from other folks here, it would turn out more of a voting, it would not be a proof. It would just give increased probability that your program is correct, if several independent implementations come up with the same result. Of course all implementations could err :-) The more agree the better. And the more diverse the implementations are, the better. E.g. you could use different programming languages, algebraic systems or a friend with time and paper and pencil and Wikipedia. :-)

Another means is to add checks to your intermediate steps, to get more confidence in your result. Kind of building a chain of trust.

You could output the prime factors you determined and compare it with the output of a prime factorization program which is known to work.
Then you check if your summing works.
Finally you could check if the primality test you apply to the candidate sums is working correctly by feeding it with known prime numbers and non prime numbers and so on.

That is kind of what folks do with unit testing for example. Trying to cover most parts of the code as working, hoping if the parts work, that the whole will work.

Or you could formally prove your program step by step, using Hoare Calculus for example or another formal method. But that is tricky, and you might end up shifting program errors to errors in the proof.

And today, in the era of internet, of course, you could internet search for the solution:

Try searching for sum of prime factors is prime in the online encyclopedia of integer sequences, which should give you series A100118. :-) It is the problem with multiplicity, but shows you what the number theory pros do, with Mathematica and program fragments to calculate the series, the argument for the case of 1 and literature. Quite impressive.

Question 2

Here's the answer I get. I exclude 1 as it has no prime divisors so their sum is 0, not a prime.

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)]

You could hard-code this list in and test against it. I'm pretty confident these results are without error.

(read . is "of").