P.E.3: Largest Prime Factor

Computer Science Level 1

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

What is the largest prime factor of the number 600851475143 ?


The answer is 6857.

Arvind Srinivasan by Arvind Srinivasan , 26, India

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

3 solutions

Swapnil Bhargava
Sep 21, 2014

Here's my C++ code 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
 
#include<iostream>
#include<cmath>
#define num 600851475143
using namespace std;
bool checkPrime(long long int n)
{
    if(n==1)
        return false;
    long long int i=sqrt(n);
    for(;i>=2;i--)
    {
        if(n%i==0)
            return false;
    }
    return true;
}
int main()
{
    long long int i=sqrt(num),sol=0;
    for(;i>=2;i--)
    {
        if(num%i==0 && (i%6==1 || i%6==5)) //Excluding 2 and 3  //every prime number is of the form 6n+1 or 6n-1
        {
            if(checkPrime(i))
            {
                sol=i;
                break;
            }
        }
    }
    cout<<sol;
    return 0;
}

1 Helpful 0 Interesting 0 Brilliant 0 Confused
Brock Brown
Jan 4, 2015

9 lines of Python should do just fine. 

1
2
3
4
5
6
7
8
9
 
num = 600851475143
factors = set()
i = 2
while i <= num:
    while num % i == 0:
        factors.add(i)
        num = num / i
    i += 1
print "Answer:", max(factors)

0 Helpful 0 Interesting 0 Brilliant 0 Confused
Arvind Srinivasan
Sep 18, 2014

My Python code is as follows: 

"""
Euler Problem #3
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?"""
factor_list=[]
n=9999
for i in range(2,n+1):
    prime=True
    for j in range(2,i):
        if i%j==0:
            prime=False
            break
    if prime==True:       
        num= 600851475143
        if num % i==0:
           factor_list.append(i)
factor_list.sort()
print "The largest prime factor of the number 600851475143 is: "
print factor_list.pop()

Hope this helps!

0 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...