Why does setting the condition to x*x < n not work in finding prime factors?

[CrazyNeutrino]

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:

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

 

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

 

[CrazyNeutrino]

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?

 

[rcgldr]

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.