埃氏篩法 Sieve of Eratosthenes

[shyangs]

import java.util.*;

public class PrimeSieve {

	public static LinkedList<Integer> sieve(int n) {
		if (n < 2) { return new LinkedList<Integer>(); }

		LinkedList<Integer> primes = new LinkedList<Integer>();
		LinkedList<Integer> nums = new LinkedList<Integer>();

		// nums = [2, 3, 4, 5, 6, 7, ..., n]
		for (int i = 2; i <= n; i++) { 
			nums.add(i);
		}

		// 從 nums移除所有 2 的倍數, 把 2 放入primes
		// 從 nums移除所有 3 的倍數, 把 3 放入primes
		// 從 nums移除所有 5 的倍數, 把 5 放入primes
		// ...
		while (nums.size() > 0) {
			int nextPrime = nums.remove();
			for (int i = nextPrime * nextPrime; i <= n; i += nextPrime) {
				nums.removeFirstOccurrence(i);
			}
			primes.add(nextPrime);
		}
		return primes;
	}

	public static void main(String[] args) {
		System.out.println("Please input an integer: ");
		Scanner scanner = new Scanner(System.in);
		System.out.println( sieve( scanner.nextInt() ) );
		if (scanner != null) { scanner.close(); }
	}
}

• Sieve of Eratosthenes - Wikipedia
• Sieve of Eratosthenes - Rosetta Code