Unable to run program

Question

So I am trying to find the largest prime factor of a fairly large number. This is a question on Project Euler (http://projecteuler.net/problem=3). My problem is that when I do compile and run my program, the command prompt comes up empty, its just a black with no text on it.

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

using namespace std;
vector <int> factors;

bool isPrime(int number)
{
    bool prime = true;
    int maxIndex=number/2;
    for (int index=2; index <= maxIndex; index++)
    {
        if (number % index == 0)
        {
            prime = false;
            break;
        }
    }
    return prime;
}

int Facts()
{
    float num = 600851475143;
    for (double i=1000000; i<=num; i++)         
    {
        if (fmod(num,i)==0)
            factors.push_back(i);
    }
}

int main()
{
    Facts();

    for (int i=0; i<factors.size(); i++)
    {
        if (isPrime(factors[i]))
            cout << i << ", " ;
    }
    return 0;
}

It has occurred to me that maybe the program is taking a long time because the operation I'm asking it to do is rather time consuming. If that is the case, is there a faster way I can find the answer to this question? I don't see a problem with my code, but if anyone else does catch a problem, feel free to change it.

You will find many discussions of this problem by doing a search for the number in the problem, http://stackoverflow.com/search?q=600851475143 — Lutz Lehmann, Mar 08 '14 at 11:24
possible duplicate of [Project Euler Question 3 Help](http://stackoverflow.com/questions/201374/project-euler-question-3-help) — starblue, Mar 08 '14 at 20:21
It seems recently every other question in the `project-euler` tag is about this problem. Please put some more effort into thinking and research before you ask a question! — starblue, Mar 08 '14 at 20:25

score 3 · Answer 1 · edited May 23 '17 at 12:20

Your program only does output when it finds results. It doesn't find any.

The prime factors of 600851475143 are 71×839×1471×6857. In Facts you are only looking for factors that are larger than 1000000.

And yes, your brute force method of going through all numbers less than the target and checking if they are a factor and then checking if they are primes is a very very slow method. See this question for faster algorithms.

Floats lose precision in calculations, and also are not guaranteed to have an accurate representation of integers larger than 16777216 (may depend on your platform). Therefore comparing the result of fmod to zero with equality is not going to work well. You should always use an epsilon value to test if a float is close to a another value. See Comparing floating point numbers and What Every Computer Scientist Should Know About Floating-Point for details.

You could use a long long instead and use integer calculations. operator% is probably faster than fmod too.

Also, if your program did find something, it would only output the array index of the result which I assume would not be very useful.

Of the algorithms found on that link, I particularly recommend the Pollard-Rho algorithm. Easy to implement and the proofs-of-correctness are manageable even for those new to the subject (in contrast to the complexity of the Quadratic Sieve). — Zéychin, Mar 07 '14 at 22:17

Unable to run program

1 Answers1