package problems;

import java.util.Arrays;

public class Problem_010c {

    /**
     * HAHAHA WOW, THIS EXECUTES FAST! Damn... I really need to learn proper arrays! :D
     *
     * Kudos to dplass1 from America.
     *
     *
     * So how does this work exactly?... Lets look at it, hard!
     *
     *
     */


        public static void main(String[] args) {

            int n = 800000000;                              // Create and initialize integer n, 2 million. This is the "range" to search in.

            boolean isPrime[] = new boolean[n+1];           // Create an array that holds n+1 boolean values.

            Arrays.fill(isPrime, true);                     // Set ALL n+1 values in the isPrime Array to: TRUE.
            isPrime[2] = true;                              // Set value at index 2, to true.
            isPrime[3] = true;                              // Set value at index 3, to true. This is needed because what follows, you will understand once you've read the rest.


                                                            // From here on the code is setting some values to false, I think the thought is that once you have done this
                                                            // only primes will remain, and adding them up is trivial.


            for (int i = 4; i < n; i += 2) isPrime[i] = false;  // Set all indexes from 4, and then every 2 slots to false. (This is basically a sieve, I'm starting to see.)
                                                                // What this does is set all even indexes from 4 and up in the array to false. Because index 2 should be true.

         // This looks like the prime finding code, a sieve!

            for (int i = 3; i < n; i += 2) {                // For i = 3 to n (the test-range), incrementing by 2, do the following. i = (3,5,7,9,11,13,15,17,19,21,23..)
                                                            // While there are some primes listed there, none of these are "actually" put to false here.

                for (int j = i+i; j < n; j += i) {          // For all j = i+i up to n, incrementing by i.  When i = 3 then j =  (6,9,12,15,18,21,24,27...)
                    isPrime[j] = false;                     //                                              When i = 5 then j =  (10,15,20,25,30,35,40,45...)
                }                                           //                                              When i = 7 then j =  (14,21,28,35,42,49,56,63...)
                                                            // What this is doing is setting all values representing multiples of odd numbers in the array to false. Clever!
            }                                               // This of course includes multiples of all possible primes in the range provided.

                                                            // When this has been done for all multiples of odd numbers, and all even numbers in the array only
                                                            // values with an address that is prime should remain. (In other words have the value TRUE.)


            long sum = 0;                                   // Create and initialize a counter variable to get our total sum with.

            for (int i = 2; i < n; ++i) {                   // For all i = 2 up to n, incrementing by 1
                if (isPrime[i]) sum += i;                   // If the value in the array at index number i is true, then add i to the counter, because the array is telling it
                                                            // that its a prime... :D
            }
            System.out.println("The sum is: " +sum);                        // Print the sum.
        }


}