Project Euler solution: 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 ?

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
}
}
}
``````
﻿

New Exercises:R Programming