1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

package com.google.code.projecteuler;


/**
 * The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
 * 
 * Find the sum of all the primes below two million.
 * 
 * @link <a
 *       href="http://projecteuler.net/index.php?section=problems&id=10">Problem
 *       10</a>
 * @link <a href="http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes">Sieve of
 *       Eratosthenes</a>
 * @author Cesar Arevalo
 */
public class Problem010_SieveOfErastothenes {

	public static void main(String[] args) {
		StopWatch stopWatch = new StopWatch();
		stopWatch.start();

		int limit = 2000000;
		long squareOfLimit = Double.valueOf(Math.sqrt(limit)).longValue();
		long sumOfPrimes = 0;
		int numberInIteration = 0;
		long squareOfi = 0;

		int[] numbers = new int[limit];

		// 1. Consider a contiguous list of numbers from two to some maximum.
		for (int i = 2; i <= limit; i++) {
			numbers[i - 2] = i;
		}

//		for (Integer number : numbers) {
//			System.out.println("number: " + number);
//		}
//		System.out.println("---");

		// 2. Strike off all multiples of 2 greater than 2 from the list.
		int numberToStrikeOff = 0;
		int index2 = 2;

		for (int i = 1; i < squareOfLimit; i++) {
			numberToStrikeOff = i + 1;
			squareOfi = i * i;

			index2 = i;
			while (index2 < numbers.length) {
				numberInIteration = numbers[index2];
				if (numberInIteration < squareOfi) {
				}
				else if (numberInIteration % numberToStrikeOff == 0) {
					numbers[index2] = 0;
				}
				index2++;
			}

//			for (Integer number : numbers) {
//				System.out.println("number: " + number);
//			}
//			System.out.println("---");
		}

		for (Integer number : numbers) {
			sumOfPrimes += number;
//			System.out.println("number: " + number);
		}
//		System.out.println("---");

		stopWatch.stop();
		System.out.println("time taken: " + stopWatch.getTime());
		System.out.println("sumOfPrimes: " + sumOfPrimes);
	}
}