Project Euler Problem 5: Smallest multiple

Problem

 2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

 What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Solution

Attempt 1: Count the occurrences of the prime factor for each number, and multiply them all.

      private static Map<Integer, Integer> primeNumberOccurrence = new HashMap<>();  
      public static void main(String[] args) {  
           for (int i=2; i<=20; i++){  
                updatePrimeNumberOccurrence(i);  
           }  
           int total = 1;  
           for (int key : primeNumberOccurrence.keySet()){  
                int occurrence = primeNumberOccurrence.get(key);  
                total *= Math.pow(key, occurrence);  
           }  
           System.out.println(total);  
      }  
      private static void updatePrimeNumberOccurrence(int number){  
           int divisor = 2;  
           int divisorCount = 0;  
           while(number > 1){  
                if(number % divisor == 0){  
                     number = number / divisor;  
                     divisorCount++;  
                }else{  
                     update(divisor, divisorCount);  
                     divisor++;  
                     divisorCount = 0;  
                }  
           }  
           update(divisor, divisorCount);  
      }  
      private static void update(int divisor, int divisorCount){  
           if (divisorCount != 0){  
                int oldCount = primeNumberOccurrence.get(divisor) != null ? primeNumberOccurrence.get(divisor) : 0;  
                if (divisorCount > oldCount){  
                     primeNumberOccurrence.put(divisor, divisorCount);  
                }  
           }  
      }  

Attempt 2: Use greatest common factor

      private static final int NUMBER = 20;  
      public static void main(String[] args) {  
           int total = NUMBER;  
           for (int i = NUMBER-1; i >= 2; i--){  
                //greatest common factor  
                total *= i / BigInteger.valueOf(total).gcd(BigInteger.valueOf(i)).intValue();  
           }  
           System.out.println(total);  
      }  

Project Euler Problem 4: Largest palindrome product

Problem

A palindromic number reads the same both ways.

The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99. Find the largest palindrome made from the product of two 3-digit numbers.

Solution

The efficiency of checking if a number is palindrome can certainly be improved, but I am more focused on optimization on two for loops.

• Start from 999 backwards, and start j=i instead of 999
• Check product > current largest palindrome first instead of checking product is palindrome first
• break inner loop when we know the rest product cannot be larger than the current largest palindrome

      public static void main(String[] args) {  
           long largestPalindrome = 0;  
           for (int i = 999; i >= 100; i--){  
                for (int j = i; j >= 100; j--){  
                     long product = i * j;  
                     if (product > largestPalindrome){  
                          if (isPalindrome(product)){  
                               largestPalindrome = product;  
                               break;  
                          }  
                     }else{  
                          break;  
                     }  
                }  
           }  
           System.out.println(largestPalindrome);  
      }  
      private static boolean isPalindrome(long product) {  
           String s = String.valueOf(product);  
           return reverse(s).equals(s);  
      }  
      private static String reverse(String s) {  
           String r = "";  
           for (int i=s.length()-1; i>=0; i--){  
                r += s.charAt(i);  
           }  
           return r;  
      }  

Project Euler Problem 3: Largest prime factor

Problem

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

What is the largest prime factor of the number 600851475143?

Solution


If the while loop condition changes to divisor < number, it will be extremely slow for number like 600851475145

      public static void main(String[] args) {            
           long number = 600851475143L;  
           long divisor = 2;  
           while((divisor * divisor) <= number){  
                if(number%divisor==0){  
                     number = number/divisor ;  
                }  
                divisor++;  
           }  
           System.out.println(number);  
      }