So i just started learning c++ this week, and one of the practice problems, from jumping into c++, is to design a program that finds all numbers from 1 to 1000 whose prime factors, when added
together, sum up to a prime number (for example, 12 has prime factors of 2, 2, and 3, which
sum to 7, which is prime). Implement the code for that algorithm.
below is the code I have, and the output I get. It works mostly, but skips some numbers, like the number 8 and I can't figure out why.
/*
Process for finding the all the numbers whose prime factors add up to a prime number.
1. Take a number
2. Divide the number by each number less than it, and test to see if returns a remainder of 0.
3. If it returns a remainder of zero, test to see if it is prime.
4. If it is prime assign it to a variable, and divide the original number by the divisor
5. Test to see if the new divided number is prime.
6. If it is not repeat the process.
7. If the new number is prime, add it to the sum of the factors.
8. Test to see if the sum of the factors is prime.
9. If it is prime, print out the original number.
*/
#include <iostream>
usingnamespace std;
bool isPrime (int number);
bool isPrimeDivisible (int number, int divisor);
int main()
{
for (int i = 0; i < 100; i++)
{
int factorSum = 0;
int newNumber = i;
for (int divisor = 2; divisor < i; divisor++)
{
if (i % divisor == 0 && isPrime(divisor))
{
factorSum = factorSum + divisor;
newNumber = newNumber / divisor;
if (isPrime(newNumber))
{
factorSum = factorSum + newNumber;
cout << "The factor sum of " << i << " equals " << factorSum << endl;
if (isPrime(factorSum))
{
cout << "The factor sum of " << i << " is prime." << endl;
cout << "\n\n";
break;
}
else
{
cout << "The factor sum of " << i << " is not prime." << endl;
cout << "\n\n";
}
}
}
}
}
}
bool isPrime(int number) // Checks to see if a number is prime
{
for (int i = 2; i < number; i++)
{
if (isPrimeDivisible(number, i))
{
returnfalse;
}
}
returntrue;
}
bool isPrimeDivisible (int number, int divisor) /* Division function for isPrime. Returns numbers with a remainder of zero.*/
{
return number % divisor == 0;
}
The factor sum of 4 equals 4
The factor sum of 4 is not prime.
The factor sum of 6 equals 5
The factor sum of 6 is prime.
The factor sum of 9 equals 6
The factor sum of 9 is not prime.
The factor sum of 10 equals 7
The factor sum of 10 is prime.
The factor sum of 12 equals 7
The factor sum of 12 is prime.
The factor sum of 14 equals 9
The factor sum of 14 is not prime.
The factor sum of 14 equals 17
The factor sum of 14 is prime.
The factor sum of 15 equals 8
The factor sum of 15 is not prime.
The factor sum of 15 equals 14
The factor sum of 15 is not prime.
The factor sum of 18 equals 8
The factor sum of 18 is not prime.
The factor sum of 20 equals 9
The factor sum of 20 is not prime.
The factor sum of 21 equals 10
The factor sum of 21 is not prime.
The factor sum of 21 equals 18
The factor sum of 21 is not prime.
The factor sum of 22 equals 13
The factor sum of 22 is prime.
The factor sum of 25 equals 10
The factor sum of 25 is not prime.
The factor sum of 26 equals 15
The factor sum of 26 is not prime.
The factor sum of 26 equals 29
The factor sum of 26 is prime.
The factor sum of 28 equals 11
The factor sum of 28 is prime.
The factor sum of 30 equals 10
The factor sum of 30 is not prime.
The factor sum of 30 equals 16
The factor sum of 30 is not prime.
The factor sum of 33 equals 14
The factor sum of 33 is not prime.
The factor sum of 33 equals 26
The factor sum of 33 is not prime.
The factor sum of 34 equals 19
The factor sum of 34 is prime.
The factor sum of 35 equals 12
The factor sum of 35 is not prime.
The factor sum of 35 equals 20
The factor sum of 35 is not prime.
The factor sum of 38 equals 21
The factor sum of 38 is not prime.
The factor sum of 38 equals 41
The factor sum of 38 is prime.
The factor sum of 39 equals 16
The factor sum of 39 is not prime.
The factor sum of 39 equals 30
The factor sum of 39 is not prime.
The factor sum of 42 equals 12
The factor sum of 42 is not prime.
The factor sum of 42 equals 20
The factor sum of 42 is not prime.
The factor sum of 44 equals 15
The factor sum of 44 is not prime.
The factor sum of 45 equals 11
The factor sum of 45 is prime.
The factor sum of 46 equals 25
The factor sum of 46 is not prime.
The factor sum of 46 equals 49
The factor sum of 46 is not prime.
The factor sum of 49 equals 14
The factor sum of 49 is not prime.
The factor sum of 50 equals 12
The factor sum of 50 is not prime.
The factor sum of 51 equals 20
The factor sum of 51 is not prime.
The factor sum of 51 equals 38
The factor sum of 51 is not prime.
The factor sum of 52 equals 17
The factor sum of 52 is prime.
The factor sum of 55 equals 16
The factor sum of 55 is not prime.
The factor sum of 55 equals 28
The factor sum of 55 is not prime.
The factor sum of 57 equals 22
The factor sum of 57 is not prime.
The factor sum of 57 equals 42
The factor sum of 57 is not prime.
The factor sum of 58 equals 31
The factor sum of 58 is prime.
The factor sum of 60 equals 12
The factor sum of 60 is not prime.
The factor sum of 62 equals 33
The factor sum of 62 is not prime.
The factor sum of 62 equals 65
The factor sum of 62 is not prime.
The factor sum of 63 equals 13
The factor sum of 63 is prime.
The factor sum of 65 equals 18
The factor sum of 65 is not prime.
The factor sum of 65 equals 32
The factor sum of 65 is not prime.
The factor sum of 66 equals 16
The factor sum of 66 is not prime.
The factor sum of 66 equals 28
The factor sum of 66 is not prime.
The factor sum of 68 equals 21
The factor sum of 68 is not prime.
The factor sum of 69 equals 26
The factor sum of 69 is not prime.
The factor sum of 69 equals 50
The factor sum of 69 is not prime.
The factor sum of 70 equals 14
The factor sum of 70 is not prime.
The factor sum of 70 equals 22
The factor sum of 70 is not prime.
The factor sum of 74 equals 39
The factor sum of 74 is not prime.
The factor sum of 74 equals 77
The factor sum of 74 is not prime.
The factor sum of 75 equals 13
The factor sum of 75 is prime.
The factor sum of 76 equals 23
The factor sum of 76 is prime.
The factor sum of 77 equals 18
The factor sum of 77 is not prime.
The factor sum of 77 equals 30
The factor sum of 77 is not prime.
The factor sum of 78 equals 18
The factor sum of 78 is not prime.
The factor sum of 78 equals 32
The factor sum of 78 is not prime.
The factor sum of 82 equals 43
The factor sum of 82 is prime.
The factor sum of 84 equals 14
The factor sum of 84 is not prime.
The factor sum of 85 equals 22
The factor sum of 85 is not prime.
The factor sum of 85 equals 40
The factor sum of 85 is not prime.
The factor sum of 86 equals 45
The factor sum of 86 is not prime.
The factor sum of 86 equals 89
The factor sum of 86 is prime.
The factor sum of 87 equals 32
The factor sum of 87 is not prime.
The factor sum of 87 equals 62
The factor sum of 87 is not prime.
The factor sum of 90 equals 13
The factor sum of 90 is prime.
The factor sum of 91 equals 20
The factor sum of 91 is not prime.
The factor sum of 91 equals 34
The factor sum of 91 is not prime.
The factor sum of 92 equals 27
The factor sum of 92 is not prime.
The factor sum of 93 equals 34
The factor sum of 93 is not prime.
The factor sum of 93 equals 66
The factor sum of 93 is not prime.
The factor sum of 94 equals 49
The factor sum of 94 is not prime.
The factor sum of 94 equals 97
The factor sum of 94 is prime.
The factor sum of 95 equals 24
The factor sum of 95 is not prime.
The factor sum of 95 equals 44
The factor sum of 95 is not prime.
The factor sum of 98 equals 16
The factor sum of 98 is not prime.
The factor sum of 99 equals 17
The factor sum of 99 is prime.
So why is it skipping 8? Let's step through the code.
1 2 3 4 5 6 7 8 9 10
i = 8.
newNumber = 8
for loop:
divisor = 2
is (8%divisor == 0)? --> yes
is divisor(2) prime? --> yes, go into if-statement body
newNumber = 8 (AKA i) / 2 (AKA divisor)
newNumber therefore == 4
is newNumber prime?
4 is not prime, so it never executes the stuff insideif (isPrime(newNumber)) when i == 8
Similar things are probably happening for the other numbers, having all of those nested if statements is probably leading to a lot of confusion, I would either separate your code into functions more or re-evaluate when things needs to be checked (for primality or divisibility, etc).
In my opinion, doing Project Euler-esque stuff is not the best way to learn a language (except Mathematica) because you'll get bogged down by the math instead of the actual language.
