/** Created by Dan Walker * * Classic Sieve of Eratosthenes * Adds a prime then removes all multiples. * * Input the number you want to calculate primes up to. * Optionally, add an int on a new line after this to select * a different sieve algorithm. * * Sieve1 uses List.remove(Object) to remove non-primes. This * is a bit inefficient though, as it searches as it calls get * and equals on each element of the list, though the list is * sorted so its probably as efficient as remove can be. * * Sieve2 I think is a bit more optimized. It uses an enhanced * for loop (which uses an iterator behind the scenes, which is) * more efficient than get) and changes any non-prime to a 0. * Then all 0s (and the 1) is removed from the list. Some additional * work can be done to make this quicker I think * * Additional optimization: ArrayList is given the initial size of * the list. When we call add Java checks if the ArrayList needs * extending, and allocates more space if required. This will * probably happen several times, so instead we initialize it * with the size that we know we'll need (from MAX) */ import java.util.*; public class Program { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int max = sc.nextInt(); Sieve sieve = null; if (sc.hasNextInt()) { int sieveType = sc.nextInt(); if (sieveType == 1) { System.out.println("Using Sieve1"); sieve = new Sieve1(max); } else { System.out.println("Using Sieve2"); sieve = new Sieve2(max); } } System.out.println(sieve.calculatePrimes()); } } interface Sieve { List calculatePrimes(); } class Sieve1 implements Sieve { private final int MAX; public Sieve1(int max) { MAX = max; } public List calculatePrimes() { List nums = new ArrayList<>(MAX); for(int i = 2; i <= MAX; i++) { nums.add(i); } for (int i = 0; i < nums.size(); i++) { int currentNum = nums.get(i); for(int j=2;currentNum*j <= MAX;j++) { Integer numToRemove = currentNum * j; nums.remove(numToRemove); } } return nums; } } class Sieve2 implements Sieve { private final int MAX; public Sieve2(int max) { MAX = max; } public List calculatePrimes() { List nums = new ArrayList<>(MAX); for(int i = 0; i <= MAX; i++) { nums.add(i); } for (Integer i : nums) { if (i == 0 || i == 1) continue; int multiplesOf = i; for(int j=2*multiplesOf; j <= MAX; j += multiplesOf) { nums.set(j, 0); } } return tidyList(nums); } private List tidyList(List list) { List primes = new ArrayList<>(MAX / 2); for (Integer i : list) { if (i > 1) primes.add(i); } return primes; } }

Sieve of Eratosthenes (Multiple algorithms)