Project Euler – Problem # 3 – Solved with Java & Python

Find the largest prime factor of a composite number.

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

What is the largest prime factor of the number 600851475143 ?

**********

The question is: “How many prime numbers do we need to try?” I used the square root of n 600851475143. That would be 775146.099225. The algorithm to find the prime number list came from a third party for both the python solution and the java solution. Once we have the list of primes, we can apply the algorithm for finding the prime factors. The largest number in the Factors list is the answer to problem 3.

I have been learning Java from internet tutorials. If you see some code that can be improved on, feel free to leave a comment.

Helpful Links:

• Prime Factor – http://en.wikipedia.org/wiki/Prime_factor
• Prime factorization algorithm – http://www.indopedia.org/index.php?title=Prime_factorization_algorithm
• A fast prime number list generator for python – http://code.activestate.com/recipes/366178/
• A java prime number list generator – http://techdive.in/java/java-prime-number

One Possible Soultion: Java

import java.util.ArrayList;
import java.util.List;

public class Problem_3 {
	public static void main(String args[])
	{
		Problem_3 prob_3Obj = new Problem_3(); // Create Problem_3 object
		long number = 600851475143L; // Large composite number
		double sqrtNumber = Math.sqrt(number) + 1; // Find the sqrt of number
		int sN = (int)sqrtNumber; // Make the sqrt an integer
		List<Integer> primes = prob_3Obj.getListOfPrimes(sN); // Generates a list of primes up to sqrt
		List<Integer> Factors = new ArrayList<Integer>(); // Create a list for the prime factors
		for(int i = 0; i < primes.size(); i++) // For loop up to the size of primes list
		{
			int prime = primes.get(i); // Gets the (i)th element in the primes list
			if(prime == 1) // 1 is not a prime
			{
				continue;
			}
			int s = 1; // Counter for while loop
			while(s == 1)
			{
				if(number % prime == 0) // If number modulus prime is equal 0
				{
					Factors.add(prime); // Add that prime to the prime factors list
					number = number / prime; // Find the next number according to the algorithm
				} else 
				{
					s = 0; // if we are done with that prime, breaks the while loop
				}
				
			}
		}
		System.out.println(Factors); // Prints out the prime factors of number
	}
	
// Start: http://techdive.in/java/java-prime-number
// Returns 1 as a prime - accounted for that in the main method
	
		public boolean isPrime(int n)
        {
        int k = (int) Math.sqrt(n);
                for (int i = 2; i <= k; i++)
                {
                        if (n % i == 0)
                                return false;
                }
                return true;
        }

        public List<Integer> getListOfPrimes(int end)
        {
                List<Integer> lstInt = new ArrayList<Integer>();

                lstInt.add(1);
                lstInt.add(2);
                boolean flag = true;

                for (int i = 3; i < end; i++)
                {
                        flag = true;
                        int sqI = (int)Math.sqrt(i);
                        for (int j = 1; j < lstInt.size(); j++)
                        {
                                if (i % lstInt.get(j) == 0)
                                {
                                        flag = false;
                                        break;
                                }

                                if (sqI < lstInt.get(j))
                                {
                                        break;
                                }
                        }
                        if (flag == true)
                        {
                                lstInt.add(i);
                        }
                }
                return lstInt;
        }
// End: http://techdive.in/java/java-prime-number
	
	}

One Possible Solution: Python

# Python version = 2.7.2
# Platform = win32

def primes(n):
    """Prime number generator up to n - (generates a list)"""
    ## {{{ http://code.activestate.com/recipes/366178/ (r5)
    if n == 2: return [2]
    elif n < 2: return []
    s = range(3, n + 1, 2)
    mroot = n ** 0.5
    half = (n + 1) / 2 - 1
    i = 0
    m = 3
    while m <= mroot:
        if s[i]:
            j = (m * m - 3) / 2
            s[j] = 0
            while j < half:
                s[j] = 0
                j += m
        i = i + 1
        m = 2 * i + 3
    return [2]+[x for x in s if x]

   ## end of http://code.activestate.com/recipes/366178/ }}}

def main():
    """Main Program - Integer factorization"""
    number = 600851475143
    primeList = primes(int(math.sqrt(number)))
    Factors = []
    for prime in primeList:
        s = 1
        while s == 1:
            if number % prime == 0:
                Factors.append(prime)
                number = number / prime
            else:
                s = 0
    print Factors
           
if __name__ == '__main__':
    import math
    main()