| /trunk/euler/src/com/google/code/projecteuler/Problem010_SieveOfErastothenes.java r17 | /trunk/java/src/com/google/code/projecteuler/Problem010_SieveOfErastothenes.java r20 | ||
| 1 | package com.google.code.projecteuler; | 1 | package com.google.code.projecteuler; |
|---|---|---|---|
| 2 | 2 | ||
| 3 | 3 | ||
| 4 | /** | 4 | /** |
| 5 | * The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17. | 5 | * The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17. |
| 6 | * | 6 | * |
| 7 | * Find the sum of all the primes below two million. | 7 | * Find the sum of all the primes below two million. |
| 8 | * | 8 | * |
| 9 | * @link <a | 9 | * @link <a |
| 10 | * href="http://projecteuler.net/index.php?section=problems&id=10">Problem | 10 | * href="http://projecteuler.net/index.php?section=problems&id=10">Problem |
| 11 | * 10</a> | 11 | * 10</a> |
| 12 | * @link <a href="http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes">Sieve of | 12 | * @link <a href="http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes">Sieve of |
| 13 | * Eratosthenes</a> | 13 | * Eratosthenes</a> |
| 14 | * @author Cesar Arevalo | 14 | * @author Cesar Arevalo |
| 15 | */ | 15 | */ |
| 16 | public class Problem010_SieveOfErastothenes { | 16 | public class Problem010_SieveOfErastothenes { |
| 17 | 17 | ||
| 18 | public static void main(String[] args) { | 18 | public static void main(String[] args) { |
| 19 | StopWatch stopWatch = new StopWatch(); | 19 | StopWatch stopWatch = new StopWatch(); |
| 20 | stopWatch.start(); | 20 | stopWatch.start(); |
| 21 | 21 | ||
| 22 | int limit = 2000000; | 22 | int limit = 2000000; |
| 23 | long squareOfLimit = Double.valueOf(Math.sqrt(limit)).longValue(); | 23 | long squareOfLimit = Double.valueOf(Math.sqrt(limit)).longValue(); |
| 24 | long sumOfPrimes = 0; | 24 | long sumOfPrimes = 0; |
| 25 | int numberInIteration = 0; | 25 | int numberInIteration = 0; |
| 26 | long squareOfi = 0; | 26 | long squareOfi = 0; |
| 27 | 27 | ||
| 28 | int[] numbers = new int[limit]; | 28 | int[] numbers = new int[limit]; |
| 29 | 29 | ||
| 30 | // 1. Consider a contiguous list of numbers from two to some maximum. | 30 | // 1. Consider a contiguous list of numbers from two to some maximum. |
| 31 | for (int i = 2; i <= limit; i++) { | 31 | for (int i = 2; i <= limit; i++) { |
| 32 | numbers[i - 2] = i; | 32 | numbers[i - 2] = i; |
| 33 | } | 33 | } |
| 34 | 34 | ||
| 35 | // for (Integer number : numbers) { | 35 | // for (Integer number : numbers) { |
| 36 | // System.out.println("number: " + number); | 36 | // System.out.println("number: " + number); |
| 37 | // } | 37 | // } |
| 38 | // System.out.println("---"); | 38 | // System.out.println("---"); |
| 39 | 39 | ||
| 40 | // 2. Strike off all multiples of 2 greater than 2 from the list. | 40 | // 2. Strike off all multiples of 2 greater than 2 from the list. |
| 41 | int numberToStrikeOff = 0; | 41 | int numberToStrikeOff = 0; |
| 42 | int index2 = 2; | 42 | int index2 = 2; |
| 43 | 43 | ||
| 44 | for (int i = 1; i < squareOfLimit; i++) { | 44 | for (int i = 1; i < squareOfLimit; i++) { |
| 45 | numberToStrikeOff = i + 1; | 45 | numberToStrikeOff = i + 1; |
| 46 | squareOfi = i * i; | 46 | squareOfi = i * i; |
| 47 | 47 | ||
| 48 | index2 = i; | 48 | index2 = i; |
| 49 | while (index2 < numbers.length) { | 49 | while (index2 < numbers.length) { |
| 50 | numberInIteration = numbers[index2]; | 50 | numberInIteration = numbers[index2]; |
| 51 | if (numberInIteration < squareOfi) { | 51 | if (numberInIteration < squareOfi) { |
| 52 | } | 52 | } |
| 53 | else if (numberInIteration % numberToStrikeOff == 0) { | 53 | else if (numberInIteration % numberToStrikeOff == 0) { |
| 54 | numbers[index2] = 0; | 54 | numbers[index2] = 0; |
| 55 | } | 55 | } |
| 56 | index2++; | 56 | index2++; |
| 57 | } | 57 | } |
| 58 | 58 | ||
| 59 | // for (Integer number : numbers) { | 59 | // for (Integer number : numbers) { |
| 60 | // System.out.println("number: " + number); | 60 | // System.out.println("number: " + number); |
| 61 | // } | 61 | // } |
| 62 | // System.out.println("---"); | 62 | // System.out.println("---"); |
| 63 | } | 63 | } |
| 64 | 64 | ||
| 65 | for (Integer number : numbers) { | 65 | for (Integer number : numbers) { |
| 66 | sumOfPrimes += number; | 66 | sumOfPrimes += number; |
| 67 | // System.out.println("number: " + number); | 67 | // System.out.println("number: " + number); |
| 68 | } | 68 | } |
| 69 | // System.out.println("---"); | 69 | // System.out.println("---"); |
| 70 | 70 | ||
| 71 | stopWatch.stop(); | 71 | stopWatch.stop(); |
| 72 | System.out.println("time taken: " + stopWatch.getTime()); | 72 | System.out.println("time taken: " + stopWatch.getTime()); |
| 73 | System.out.println("sumOfPrimes: " + sumOfPrimes); | 73 | System.out.println("sumOfPrimes: " + sumOfPrimes); |
| 74 | } | 74 | } |
| 75 | } | 75 | } |
