# Project Euler problem 3

1. Aug 27, 2009

What is the largest prime factor of the number 600851475143 ?

My attempt:
Code (Text):

#include <stdafx.h>

int main()
{
int num1, num2, num3, num4, lrgprime, sum;
lrgprime=num2=num4=sum=0;
for (num1=2; num1<300425737572; num1++) {
num2=600851475143%num1;

if (num2==0) {
for (num3=2; num3<=num1; num3++) {
num4=num1%num3;
if (num4==0 && num1==num3 && num1>=lrgprime)
lrgprime=num1;
}
}
}
printf("This is the largest prime factor: %d", lrgprime);
return 0;
}
The machine is just not running this code

What did I do wrong?

2. Aug 27, 2009

### nirax

check with some smaller numbers first. see whether you get anything

3. Aug 27, 2009

### mXSCNT

Two problems. First, 600851475143 is too large to store in an int (which is usually 32 bits and only goes up to about 2 billion). Try using long longs instead of ints. Second,
Code (Text):

if (num2==0) {
for (num3=2; num3<=num1; num3++) {
num4=num1%num3;
if (num4==0 && num1==num3 && num1>=lrgprime)
lrgprime=num1;
}
}

doesn't do what you want. It eventually always sets lrgprime to num1, even when num1 has divisors. You need to use a break statement to break out of the loop if num4 == 0 and num1 != num3.

4. Aug 27, 2009

### junglebeast

1) stdafx.h is not a standard header
2) The maximum value of a 32-bit signed int is 2147483647. Of course, there is no reason to use integers for this task. The largest basic type you could use would be "unsigned long long", which has a maximum value of 18446744073709551615
3) Your code is a mess...you have tons of useless auxiliary variables and have split things into multiple lines just making it more confusing than it should be.
4) This is not an efficient approach, and will take too long on a big number.

Code (Text):
#include <iostream>
#include <limits>

typedef unsigned long long BigInt;
using namespace std;

BigInt largest_prime_factor( const BigInt &x )
{
//find factors
for(BigInt y = x/2; y>2; --y)
{
//check factors
if( x%y == 0 )
{
//check if factor is prime
for(BigInt z=2; z<y; ++z)
if( y%z == 0 )
goto not_prime;
return y;
}
not_prime: ;
}
return x;
}

int main()
{

cout << "Max value = " << numeric_limits<BigInt>::max() << "\n";
cout << largest_prime_factor( 600851475143 );
}

Last edited: Aug 27, 2009
5. Aug 28, 2009

### mathmate

Code (Text):
for(BigInt y = x/2; y>2; --y)
Just a suggestion: since the largest prime factor of x cannot not exceed x0=(int)sqrt(x), it pays to start at x0, especially for large numbers.

6. Aug 28, 2009