ProEuler P_010a

package problems;

public class Problem_010b {

    /* Pseudocode: To find the sum of all the primes below two million.
     *
     *
     *
     *  The Prime Number Theorem says that the number of primes not exceeding x can be approximated by x/ln(x).
     *
     *  So the number of primes not exceeding 2.000.000 is:
     *
     *  2.000.000/ln(2.000.000) = 137849 (Roughly)
     *
     *  This means that there are about 138 thousand give or take primes lower than 2 million.
     *
     *  I actually cheated a bit and searched for the biggest prime under 2 million using a method from problem 3 that finds the biggest prime factor of a number,
     *  if the biggest prime factor is the number you put in the number is a prime.
     *
     *  The biggest prime under 2million is 1999993.
     *
     *  Actually I could probably use that to add upp all the primes under 2 million by working my way down and checking on the way... maybe?
     *
     * Here is some more information from wikipedia:
     *
     * The simplest primality test is as follows:
     *
     * Given an input number n, check whether any integer m from 2 to n - 1 divides n.
     * If n is divisible by any m then n is composite, otherwise it is prime.
     *
     * However, rather than testing all m up to n - 1, it is only necessary to test m up to sqrt(n): if n is composite then it can be factored into two values,
     * at least one of which must be less than or equal to sqrt (n).
     *
     * The efficiency can also be improved by skipping all even m except 2, since if any even number divides n then 2 does.
     *
     *
     * It can be improved further by observing that all primes are of the form 6k ± 1, with 2 and 3 being the only exceptions.
     * This is because all integers can be expressed as (6k + i) for some integer k and for i = -1, 0, 1, 2, 3, or 4;
     * 2 divides (6k + 0), (6k + 2), (6k + 4); and 3 divides (6k + 3).
     *
     * So a more efficient method is to test if n is divisible by 2 or 3, then to check through all the numbers of form 6k ± 1 =< sqrt (n).
     * This is 3 times as fast as testing all m.
     *
     *
     *
     * Pseudocode Version 0.1
     *
     * 1. Start looking for primes, start with prime nr. 3 and increment by two. (Use while loop maybe?)
     *  1a. In the primetest, only test numbers that are smaller than the square root of the number.
     *  1b. In the primetest, only test with previously found primes.
     *
     * 2. When a prime is found check if its smaller than two million.
     *  If smaller:
     *  3a. Store it in the array.
     *  3b. Add it to the SUM variable.
     *  If larger:
     *   Stop the search/program.
     *   Print the SUM.
     *
     *   What variables do I need?
     *
     *   First off all I need a counter to get the sum of the primes.
     *
     *   long sumPrimes = 0;
     *
     *   Then I need some kind of variable to hold the number I am currently testing.
     *
     *   long testNumber = 0;
     *
     *   I am only interested in testing numbers less than 2000000, so I can set a range.
     *
     *   testRange = 2000000
     *
     *
     *
     * */

    public static void primeFinder(){


        int testRange = 2000000;
        long primeSum = 2;
        long lastPrimeSum = 2;
        long currentPrime = 0;
        int primesFound = 0;

        for( int i = testRange-1; 0 < i ; i -= 2 ){
            tryagain:
            if( i % 2 == 0 || i % 3 == 0 || i % 5 == 0 || i % 7 == 0 || i % 11 == 0 || i % 13 == 0 || i % 17 == 0 || i % 19 == 0){
                break tryagain;
            }
            lastPrimeSum = primeSum;
            currentPrime = biggestFactor(i);
            primeSum += currentPrime;

            if(lastPrimeSum < primeSum){
                primesFound++;
                if(primesFound % 1000 == 0){
                System.out.println(primesFound +" primes found, latest prime: " +currentPrime);
                }
            }

        }
        System.out.print("Final sum:" +primeSum);




    }


    public static long biggestFactor(long x)  // Returns the biggest prime factor of input.
    {
       long a = 3;
       long input = x;


       while ( x > 1 )
       {
           if ( ( x % a ) == 0 )
           {
               x = x / a;
                                                // System.out.println("a = " +a); System.out.println("x = " +x);
           }
           else
           {
              a += 2;
           }
       }

       if( a == input){
       return a;
       } else {
           return 0;
       }
    }


    public static void main(String[] args) {
        // TODO Auto-generated method stub

        primeFinder();
//      System.out.println(biggestFactor(2));


    }

}