Project Euler solution 3

  • #1
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:

Answers and Replies

  • #2
phyzguy
Science Advisor
4,645
1,583
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:
  • #3
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.
 
  • #4
phyzguy
Science Advisor
4,645
1,583
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:
  • #5
rcgldr
Homework Helper
8,713
539
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.
 
  • Like
Likes CrazyNeutrino

Related Threads on Project Euler solution 3

  • Last Post
Replies
5
Views
519
  • Last Post
Replies
14
Views
859
  • Last Post
4
Replies
97
Views
4K
  • Last Post
Replies
8
Views
4K
Replies
13
Views
1K
Replies
31
Views
3K
Replies
7
Views
584
  • Last Post
Replies
13
Views
18K
  • Last Post
Replies
5
Views
7K
Top