Project Euler - Problem 3

[thegeek101]

I have code to test for a factor then test for a prime. However, every time I run
the program it successfully finds the factors of 600851475143, but says they are all NOT prime. I know it's very inefficient but I am going for accuracy. It takes about 10 mins to get the final factor.
The first three factors (all prime) include : 71, 839, and 1471

#include <iostream>
#include <math.h>
#include <string>

using namespace std;

int main()
{
    long long div = 1;
    long num;
    long test = 3;
    // Now Obsolete : bool prime = true;
    while (div < 600851475143)
    {
        div += 2;
        if (600851475143 % div == 0)
        {
            num = div;
            // bool prime = true;
            // test = 3;
            while( (test < num - 1) && (prime) )
            {
                test += 2;
                if (num % test == 0)
                {
                    prime = false;
                }
            }
            cout << div;
            cout << " ";
            cout << prime << endl;
         }
    }
    return 0;
}

[cire]

You set prime to true on line 12. If it is ever set to false on line 24, when will it ever be true again?

You set test to 3 on line 11. If it is ever incremented on line 21, will it ever be 3 again?

I know it's very inefficient but I am going for accuracy.

They are not mutually exclusive goals.

[thegeek101]

Thanks for the tip and reminder of such an error. However, the program should only then create an error after the numbers are no longer prime. Test should not be set to 3 again as it is not contained in any of the 'while' loops.

[dhayden]

Suppose you get to line 19 when test == num-1.
The test is true
You execute test += 2. Now test = num+1
So the test at line 22 will be true and prime gets set to false.

How will prime ever get set to true again?

More importantly, the entire look at line 19 is not necessary. When you find a factor, print it out and then divide the original number by the fact, thus giving you a smaller target number. If you do it this way, any factors that you find will necessarily be prime because if they weren't, then you would have found the subfactors already.

[thegeek101]

So I have solved the problem of making sure that prime is set to true by putting it at line 18. I have also stated that test = 3 in the same area (before the 2nd 'while' loop). Also, the 'if' statement, contrary to dhayden's point, is simply testing not resetting any values for 'num'.