# Project Euler solution 3

I've just started with project Euler. The problem I just finished is phrased as follows:

"The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?"

The method i used was trial division. Here is my code in C:
C:
#include<stdio.h>
int main()
{
long long n = 600851475143;
long long x;
long long factor;

for(x=2; x<n; x++)
{
while( n % x == 0 )
{
n =  n / x;
factor = x;
}
}

printf("\n%lld\n", x);
return 0;
}
Although this did solve the problem, (answer is 6572) I have read that you only need to check for factors upto the square root of n. I tried doing this by setting the condition x*x<n instead of x<n. This however, does not work and prints a value of 1472. Can someone explain why?

Last edited by a moderator:

Related Programming and Computer Science News on Phys.org
phyzguy
Your code is wrong. Neither 6572 nor 1472 are factors of 600851475143. Notice that the variable factor is never used. I suggest getting it working on smaller numbers first. Also, think about what happens if you find a factor x, and this leads to a new value of n=n/x which is smaller than x.

Last edited:
My apologies, i meant 6857. My program generated the correct answer. Admittedly I'm not too sure why and i don't know why it doesn't work when i try x*x<n. Also, i meant to print factor, not x.

phyzguy
My apologies, i meant 6857. My program generated the correct answer. Admittedly I'm not too sure why and i don't know why it doesn't work when i try x*x<n. Also, i meant to print factor, not x.
Does your original code (with x<n) work when you print factor?

Let me ask another question. Do you realize that when you update the value of n inside the for loop, that this impacts the test (x<n or x*x<n) which is done to decide when to exit the loop?

Last edited:
rcgldr
Homework Helper
Although this did solve the problem, (answer is 6572) I have read that you only need to check for factors up to the square root of n. I tried doing this by setting the condition x*x<n instead of x<n. This however, does not work and prints a value of 1472. Can someone explain why?
600851475143 = 71×839×1471×6857.

During the loop the values for n are:

600851475143/17 = 8462696833
8462696833/839 = 10086647
10086647/1471 = 6857
6857/6857 = 1

So the check for x < n is the correct check to use in this case. If n wasn't being divided each time a factor was found, then the check for x*x < n would work.

CrazyNeutrino