Solution to Project Euler Problem 3: Largest prime factor - The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143?

• Java Code

package sikademy;
/**
 *
 * @author Archangel Macsika
 * Copyright (c) Sikademy. All rights reserved
 */

public class SikademyEulerSolution {
	
	public String run() {
		long n = 600851475143L;
		while (true) {
			long p = smallestFactor(n);
			if (p < n)
				n /= p;
			else
				return Long.toString(n);
		}
	}

	// Returns floor(sqrt(x)), for x >= 0.
	public static long sqrt(long x) {
		if (x < 0)
			throw new IllegalArgumentException("Square root of negative number");
		long y = 0;
		for (long i = 1L << 31; i != 0; i >>>= 1) {
			y |= i;
			if (y > 3037000499L || y * y > x)
				y ^= i;
		}
		return y;
	}

	// Returns the smallest factor of n, which is in the range [2, n]. The result is always prime.
	private static long smallestFactor(long n) {
		if (n <= 1)
			throw new IllegalArgumentException();
		for (long i = 2, end = sqrt(n); i <= end; i++) {
			if (n % i == 0)
				return i;
		}
		return n;

	public static void main(String[] args) {
                SikademyEulerSolution solution = new SikademyEulerSolution();
		System.out.println(solution.run());
	}	
}

• Python Code

# 
# Copyright (c) Sikademy. All rights reserved.
# @author Archangel Macsika
# 

def compute():
	n = 600851475143
	while True:
		p = smallest_prime_factor(n)
		if p < n:
			n //= p
		else:
			return str(n)


def sqrt(x):
	assert x >= 0
	i = 1
	while i * i <= x:
		i *= 2
	y = 0
	while i > 0:
		if (y + i)**2 <= x:
			y += i
		i //= 2
	return y


# Returns the smallest factor of n, which is in the range [2, n]. The result is always prime.
def smallest_prime_factor(n):
	assert n >= 2
	for i in range(2, sqrt(n) + 1):
		if n % i == 0:
			return i
	return n  # n itself is prime


if __name__ == "__main__":
	print(compute())