Input: an integer n > 1
Let A be an array of Boolean values, indexed by integers 2 to n,
initially all set to true.
for i = 2, 3, 4, ..., not exceeding √n:
if A[i] is true:
for j = i2, i2+i, i2+2i, i2+3i, ..., not exceeding n :
A[j] := false
Output: all i such that A[i] is true.
Wiki上還有動畫說明:
public class Solution { public int countPrimes(int n) { boolean[] primes = new boolean[n]; for(int i = 2; i < n; i++) primes[i] = true; for(int i = 2; i * i < n; i++) { if( primes[i] ) for(int j = i * i; j < n; j = j + i) primes[j] = false; } int primeCnt = 0; for(int i = 0; i < n; i++) if(primes[i]) primeCnt++; return primeCnt; } }
沒有留言:
張貼留言