001package net.n1da.dev.euler;
002
003import net.n1da.dev.euler.core.*;
004import net.n1da.dev.euler.helper.*;
005
006import java.util.*;
007
008/**
009 * Solution for problem 21
010 * "<strong>Amicable numbers</strong>"
011 * completed on Sun, 24 May 2015, 06:32.
012 * 
013 * @author <a href="mailto:nico@danneberg.de">Nico Danneberg</a>
014 * @since 24.05.2015 06:09:13
015 * 
016 * @see <a href="https://projecteuler.net/problem=21" target="_blank">Problem @ Project Euler</a>
017 * @see <a href="http://n1da.net/specials/projekt-euler/problem-21-befreundete-zahlen/" target="_top">Solution @ Ni-Da-Net</a>
018 */
019public class PE0021 extends Problem {
020
021        /**
022         * Stores all found amicable numbers.
023         */
024        ArrayList< Long > cache;
025        
026        /**
027         * A simple constructor to set {@link Problem#number number}
028         * and {@link Problem#title title}.
029         */
030        public PE0021() {
031                super( 21, "Amicable numbers" );
032        }
033
034        /**
035         * Just initializes the {@link #cache} as empty memory.
036         */
037        @Override
038        public void prepare() {
039                super.prepare();
040                cache = new ArrayList< Long >();
041        }
042        
043        /**
044         * Runs a loop to 10000 and checks if the current number is amicable.
045         * A found amicable number is added to final sum.
046         * 
047         * @return the sum of all found amicable numbers
048         * @see #isAmicable(int)
049         */
050        @Override
051        public String solve() {
052                long sum = 0;
053                int cur = 1;
054
055                while( cur < 10000 ) {
056                        if( isAmicable( cur ) ) {
057                                sum += cur;
058                        }
059                        cur++;
060                }
061                
062                return IO.l2s( sum );
063        }
064        
065        /**
066         * Checks the given number to be a amicable number. Therefore first
067         * the {@link #cache} is asked. If the number could not be found in
068         * {@link #cache} the {@link Mathe#getSumOfDivisors(long) sum of divisors}
069         * is calculated.
070         * 
071         * @param num the number to be checked
072         * @return true if the number is amicable
073         * @see Mathe#getSumOfDivisors(long)
074         */
075        private boolean isAmicable( int num ) {
076                if( cache.contains( num ) )
077                        return true;
078                
079                long sum = Mathe.getSumOfDivisors( num );
080                
081                if( sum != num && num == Mathe.getSumOfDivisors( sum ) ) {
082                        cache.add( sum );
083                        return true;
084                } else {
085                        return false;
086                }
087        }
088}