Syfran.com

Problem Ten

The problem is to find the sum of all the primes below 2 million.

/**
 * The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.       

Find the sum of all the primes below two million.
 * @author syfran
 * @version %I% %U% %G%
 */
//package com.syfran.Euler;                      

import java.util.ArrayList;

public class ProblemTen extends AbstractEuler
{
        public long solve()
        {
                long sum = 10;
                ArrayList<Integer> v = new ArrayList<Integer>();
                v.add(2);
                v.add(3);
                v.add(5);
                for(int c = 6; c <= 2000000; c++ )
                {
                        boolean isPrime = true;
                        for(Integer a : v)
                        {
                                if(c % a == 0)
                                {
                                        isPrime = false;
                                        break;
                                }
                                if(a > Math.sqrt(c))
                                        break;
                        }
                        if(isPrime == true)
                        {
                                v.add(c);
                                sum += c;
                        }
                }

                return sum;
        }

        public static void main(String [] w)
        {
                ProblemTen p = new ProblemTen();
                p.start();
        }
}

This Basically implements two concepts. One is that you do not need to go past the sqrt of the number you are testing before everything gets redundant.

The second is that every nonprime number can be factored down to all primes, therefore you can store the primes and only test them. ie. You do not need to test 6 after you test 2 and 3.

Runtime: 1270 ms

Possible optimizations:

None I can think of at current.

Bookmark It

Hide Sites