w3resource logo


Euler Project

Project Euler solution: Largest prime factor

Secondary Nav

Problem

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

What is the largest prime factor of the number 600851475143 ?

Result : 6857

Solution in multiple languages

PHP

<?php
$max = 600851475143;
$l_num = 0;
for ($j = floor(sqrt($max)) / 2; $j >= 2; $j--) 
{
  if (!($j % 2)) {
    continue;
  }
  $d = 3;
  $x = sqrt($j);
  while (($j % $d) && $d < $x) {
    $d += 2;
  }
  if (((!($j % $d) && $j != $d) * 1) == 0) 
  {
    if (!($max % $j)) 
	{
      $l_num = $j;
      break;
    }
  }
}
echo $l_num;
?>

Python

num = 600851475143
i = 2
while i * i < num:
     while num % i == 0:
         num = num / i
     i = i + 1
print(num)

Ruby

#!/usr/bin/env ruby

def factorize(orig)
  factors = {}
  factors.default = 0   
  n = orig
  i = 2
  sqi = 4                 
  while sqi <= n do
    while n.modulo(i) == 0 do
      n /= i
      factors[i] += 1
        end
       sqi += 2 * i + 1
    i += 1
  end

  if (n != 1) && (n != orig)
    factors[n] += 1
  end
  factors
end

puts factorize(600851475143).keys.max

C

#include <stdio.h>
#include <math.h>

#define NUMBER 600851475143

int isPrime(int ztest)
{
    int ki=0;
    int ss=( (int) sqrt(ztest) );

    for(ki = 3; ki <= ss; ki+=2)
    {
        if(ztest % ki == 0)
        {
            return 0;
        }
    }

    return 1;
}

int main()
{
    int jj=0;
    int ki=0;


    while(1)
    {
        for(ki=3; ; ki+=2)
        {
            if(isPrime(ki))
            {
                if(NUMBER%ki==0)
                    jj=ki;
                if(ki>=(sqrt(NUMBER)))
                    goto END;
            }
        }
    }

    END:
    printf("%d", jj);
    return 0;
}

JavaScript

var originalTarget = 600851475143;
var target = originalTarget;
var i = 2;
while(i<target) {
while(target%i === 0) {
(function(newtarget) {
target = newtarget;
})(target / i)
}
i++;
}
console.log(target);

Go

package main

func main() {
    target := int64(600851475143)
    arr := make([]bool, 10000)
    prime := 3
    var x int
    for {
        for x = 2 * prime; x < len(arr); x += prime {
            arr[x] = true
        }
        for x = prime + 2; x < len(arr) && arr[x]; x += 2 {
        }
        if x < len(arr) {
            prime = x
            if target%int64(x) == 0 {
                target = target / int64(x)
                if target == 1 {
                    println(x)
                    return
                }
            }
        } else {
            break
            //break the loop in case the answer is not less than 10000
        }
    }
}


Join our Question Answer community to learn and share your programming knowledge.

Help the community:

Python: Fizzbuzz

C++: Decimal to binary conversion

JavaScript: Need Help in JavaScript

Python: Help me with this program