[leetcode] find prime

不是第一次做这个题了.. 最优方法就是从2开始 把凡是2的倍数去掉..然后advance到下一个...下一个不是prime的话 继续 遇到prime继续往后灭 ..note:从2 到sqrt(n)就可以了 ..2.内部loop直接找下一个倍数 不要逐个逐个找

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

public class Solution { public int countPrimes(int n) { if (n <= 2) return 0; boolean notPrime[] = new boolean[n]; int k = (int)Math.sqrt(n); int count = 0; for (int i = 2; i <= k+2 && i < n; i++){ if (!notPrime[i]){ int multi = i*2; while (multi < n){ if (!notPrime[multi]){ notPrime[multi] = true; count++; } multi += i; } } } return n-2-count; } }