Project Euler #3 - Largest Prime Factor

It's been fun reading responses in the last two Project Euler threads. If you missed them, you can view Problem #1 and Problem #2.

Let's keep it rolling with Problem #3. Again, this is from the wonderful Project Euler.

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

What is the largest prime factor of the number 600851475143 ?

Look forward to seeing solutions in your language of choice!

Comments

[Rossman]

C#

    internal class Task3
    {
        const long number = 600851475143;
        long maxPrimeDivider = 2;
        private static bool IsPrime(long number)
        {
            for (var divisor = 2; divisor <= Math.Sqrt(number); divisor++)
            {
                if (number % divisor == 0)
                {
                    return false;
                }
            }
            return true;
        }

        public Task3() 
        {
            var numberSqrt = (long)Math.Sqrt(number);
            Parallel.For(2, numberSqrt, num =>
            {
                if (number % num == 0 && IsPrime(num) && maxPrimeDivider < num)
                {
                    maxPrimeDivider = num;
                }
            });
            Console.WriteLine(maxPrimeDivider);
        }
    }

Result

6857

[JuriTuuti]

Julia

function isprime(n)
a = ceil(Int,sqrt(n))+1
a=iseven(a) ? a+1 : a
for i = a:-2:3
if n % i == 0
return false
end
end
return true
end

function largest_prime(number)
sqrt_of_n = ceil(Int,sqrt(number)) # the answer must be less than square root of n
sqrt_of_n=iseven(sqrt_of_n) ? sqrt_of_n+1 : sqrt_of_n #a prime cannot be even, so only check odd numbers
for i = sqrt_of_n:-2:1

if number % i == 0 #if 600851475143 is divisible by i
if isprime(i) #then check if i is prime
return i
break
end
end
end
end

println(largest_prime(600851475143))

How do I enter formatted code on this site?

[Sagnik Ray]

java is cool

static long IsPrime(long n){
int counter = 2;
long newval = n;
long larfact = 0;
while(counter*counter <= n){
if(newval % counter == 0){
newval = newval/counter;
larfact = counter;
}
else{
counter++;
}
}
if(newval > larfact){
larfact = newval;
}
return larfact;

but 600851475143 is coming under the range of the "long" data type of java but still it works for any value below it .
THE APPROACH IS PRETTY SIMPLE :
I used the the "Fundamental Theorem of Arithmetic" which states That Any Integer greater than 1 is either a prime number or product of prime numbers.
For example:
12
we start with smallest prime number 2.
the 12/2 = 6 which means that 2 is the prime factor 12.
If we try again by dividing the result by 2
6/2 = 3 . 3 is also a prime number . So the complete factorization is 2,2,3.

I have implemented this logic in the above code This works really fast .I think this code can be improved
a little bit Please some one suggest me.

Hope You like The implementation ;)

[Sunday Ezeilo]

Well optimized code. You had to think a lot. Good one, bro!

[rahy-hub]

/*Largest prime factor

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

What is the largest prime factor of the number 600851475143 ?*/

include

using namespace std;

int main()
{
long long num=600851475143 ,largest=1 ;
for(int i=2;i<=num;i++)
{
if(num%i==0)
{
num=num/i;
cout< if(i>largest)
largest=i;
}

}
cout<<"\n\n"<<"the largest prime factor of the number 600851475143 is "<<largest<<"\n";
return 0;
}

My code in C++ >>Output>>6857

[Prabhjot Singh Rana]

Python:

maxnum = 600851475143  
result = 2

while maxnum > result:
    if maxnum % result == 0:
        maxnum = maxnum /result
    else:
        result = result +1

print(result)

[asterpac]

python

[khouloudzaiter]

Java

        Scanner in = new Scanner(System.in);
        System.out.printf("Enter i Value:  ");
        long n = in.nextLong();
        long number = n;
        long largestPrimeFactor = n;
        long i = 2;
        while (i <= n && n != 1) {
            if (n % i == 0) {
                n = n / i;
                largestPrimeFactor = i;
            }
            else {
                i = i+1;
            }
        }
        System.out.println("The largest prime factor of the number "+ number + " is = "+ largestPrimeFactor);

[Ali Spittel]

Python!

def list_of_primes(n):
    not_prime = set() # In is O(1) rather than O(N)
    primes = set()
    for i in xrange(2, n+1):
        if i not in not_prime:
            primes.add(i)
            # Adds multiples of the number to the set of checked values
            # i * (i-1) etc. are already updated so starts at i*i
            not_prime.update(range(i*i, n+1, i))
    return primes


def get_factors(n):
    factors = set()
    for i in xrange(1, int(n**0.5)):
        if n % i == 0:
            factors.add(i)
            factors.add(n/i)
    return list(factors)


def get_prime_factors(n):
    factors = sorted(get_factors(n), reverse=True)
    primes = list_of_primes(factors[0])
    for factor in factors:
        if factor in primes:
            return factor
    else:
        return None

print(get_prime_factors(13195))

[Tobias Salzmann]

Scala:

def factors(n: Long, current: Int) = Stream.from(current)
    .takeWhile(k => k * k <= n)
    .find(n % _ == 0)

def largestPrimeFactor(n : Long, current : Int = 2): BigInt = {
  factors(n, current) match {
    case None => n
    case Some(k) => largestPrimeFactor(n/k, k)
  }
}

largestPrimeFactor(600851475143L)