When I run this code I get the error: variable primef not initialized, but I think it is (unless I don't properly understand c++) Also, how efficient is my code in terms of processing power used? Here is the code:
/*
This program finds the largest prime factor of the number 600851475143
Written by Jay Schauer
*/
//Data Declarations
#include <iostream>
int main()
{
using namespace std;
int number = 600851475143; //stores the number
int primef; //stores the largest prime number
for (int i = 2; i < number; i++)
{
cout << "Number: " << number << endl;
cout << "i: " << i << endl;
if (number % i == 0)
{
number /= i;
primef = i;
}
cout << "Largest prime factor: " << primef << endl;
}
cout << "Largest prime factor: " << primef << endl;
system("pause");
return 0;
}
If number is even, primef is initialized to 2 the first time through the loop. However, if number is odd, primef is not initialized the first time through the loop, because the if fails, so when you try to write it in the last statement of the loop it has never been initialized.
Your algorithm is not particularly efficient. Here's pseudocode for something better; it finds all the factors, and their multiplicities, not just the largest:
function factors(n)
f := 2
while f * f <= n
while n % f == 0
output f
n := n / f
f := f + 1
if n > 1 then output n
That's still not particularly efficient, but better than yours. Once you get that working, the next step up in efficiency is to eliminate factors of 2 separately, then trial divide only by odd f.
You should have noticed that you have the same report of the largest prime factor in two different places in your code. That's a clue that something is wrong. Which one should you remove?