Project Euler Problem 3: Finding the Largest Prime Factor

[SELFMADE]

What is the largest prime factor of the number 600851475143 ?

My attempt:

#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?

 

[nirax]

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

 

[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,

		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.

 

[junglebeast]

What is the largest prime factor of the number 600851475143 ?

My attempt:

#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?

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.

#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 );
}

 

[mathmate]

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.

 

[SELFMADE]

Thank you so much, I am going to save this page up, go home and try it. I have been struggling on this problem for 3 days.