Finding prime factors

Question

#include <iostream>
using namespace std;

void whosprime(long long x)
{
    bool imPrime = true;

    for(int i = 1; i <= x; i++)
    {
        for(int z = 2; z <= x; z++)
        {
            if((i != z) && (i%z == 0))
            {
                imPrime = false;
                break;
            }
        }

        if(imPrime && x%i == 0)
            cout << i << endl;

        imPrime = true;
    }    
}

int main()
{
    long long r = 600851475143LL;
    whosprime(r);  
}

I'm trying to find the prime factors of the number 600851475143 specified by Problem 3 on Project Euler (it asks for the highest prime factor, but I want to find all of them). However, when I try to run this program I don't get any results. Does it have to do with how long my program is taking for such a large number, or even with the number itself?

Also, what are some more efficient methods to solve this problem, and do you have any tips as to how can I steer towards these more elegant solutions as I'm working a problem out?

As always, thank you!

Solution 1

Your algorithm is wrong; you don't need i. Here's pseudocode for integer factorization by trial division:

define factors(n)

    z = 2

    while (z * z <= n)

        if (n % z == 0)
            output z
            n /= z

        else
            z++

    if n > 1
        output n

I'll leave it to you to translate to C++ with the appropriate integer datatypes.

Edit: Fixed comparison (thanks, Harold) and added discussion for Bob John:

The easiest way to understand this is by an example. Consider the factorization of n = 13195. Initially z = 2, but dividing 13195 by 2 leaves a remainder of 1, so the else clause sets z = 3 and we loop. Now n is not divisible by 3, or by 4, but when z = 5 the remainder when dividing 13195 by 5 is zero, so output 5 and divide 13195 by 5 so n = 2639 and z = 5 is unchanged. Now the new n = 2639 is not divisible by 5 or 6, but is divisible by 7, so output 7 and set n = 2639 / 7 = 377. Now we continue with z = 7, and that leaves a remainder, as does division by 8, and 9, and 10, and 11, and 12, but 377 / 13 = 29 with no remainder, so output 13 and set n = 29. At this point z = 13, and z * z = 169, which is larger than 29, so 29 is prime and is the final factor of 13195, so output 29. The complete factorization is 5 * 7 * 13 * 29 = 13195.

There are better algorithms for factoring integers using trial division, and even more powerful algorithms for factoring integers that use techniques other than trial division, but the algorithm shown above will get you started, and is sufficient for Project Euler #3. When you're ready for more, look here.

Solution 2

A C++ implementation using @user448810's pseudocode:

#include <iostream>
using namespace std;

void factors(long long n) {
    long long z = 2;
    while (z * z <= n) {
        if (n % z == 0) {
            cout << z << endl;
            n /= z;
        } else {
            z++;
        }
    }
    if (n > 1) {
        cout << n << endl;
    }
}

int main(int argc, char *argv[]) {
    long long r = atoll(argv[1]);
    factors(r);
}

// g++ factors.cpp -o factors ; factors 600851475143

Perl implementation with the same algorithm is below.
Runs ~10-15x slower (Perl 0.01 seconds for n=600851475143)

#!/usr/bin/perl
use warnings;
use strict;

sub factors {
    my $n = shift;
    my $z = 2;
    while ($z * $z <= $n) {
        if ( $n % $z ) {
            $z++;
        } else {
            print "$z\n";
            $n /= $z;
        }
    }
    if ( $n > 1 ) {
        print "$n\n"
    }
}

factors(shift);

# factors 600851475143

Solution 3

600851475143 is outside of the range of an int

void whosprime(int x) //<-----fix heere ok?
{
    bool imPrime = true;

    for(int i = 1; i <= x; i++)
    {... 
      ...