##
**Problem:**

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

What is the largest prime factor of the number 600851475143 ?

##
**Solution:**

6857

##
**Code:**

The solution may include methods that will be found here: Library.java .

The solution may include methods that will be found here: Library.java .

public interface EulerSolution{ public String run(); }

/* * Solution to Project Euler problem 3 * By Nayuki Minase * * http://nayuki.eigenstate.org/page/project-euler-solutions * https://github.com/nayuki/Project-Euler-solutions */ public final class p003 implements EulerSolution { public static void main(String[] args) { System.out.println(new p003().run()); } /* * Algorithm: Divide out all the smallest prime factors except the last one. * For example, 1596 = 2 * 2 * 3 * 7 * 19. The algorithm ensures that the smallest factors will be found first. * After dividing out the smallest factors, the last factor to be found will be equal to the quotient, so it must be the largest prime factor. */ public String run() { long n = 600851475143L; while (true) { long p = smallestFactor(n); if (p < n) n /= p; else return Long.toString(n); } } private static long smallestFactor(long n) { for (long i = 2, end = Library.sqrt(n); i <= end; i++) { if (n % i == 0) return i; } return n; // Prime } }

## No comments :

## Post a Comment