LeetCode 204 Count Primes

题目链接:Count Primes

题意:求出小于n的素数个数

好久没玩leetcode了,准备每天刷一道,保持下编码状态,最近老是在看代码,没怎么写代码=。=

随后pick one,就是一道简单题。顺便复习了下线性筛

普通的写法 \(O(nlog(n))\)

欧拉筛法 \(O(n)\)

因为普通的写法中会有很多次重复筛选。

每个合数都是素数和另一个数的乘积,

而每个数都是由素数的乘积组成

如果 \(i = 8\) , 那么由于 \(i\%2 == 0\) ,因此对于 \(i=8\) 就只需要检查 \(primes[0]=2\) 即可,因为对于大于 \(primes[0]\) 的质数,像 \(3\) ,有 \(8\times 3 = 2\times 2\times 2\times 3 = 12\times 2\)

即如果 \(i\%primes[j]=0\) 那么总有一个数 \(x\) 满足 \(i\times primes[n]=x\times primes[j](n>j,x>i)\) 所以比 \(primes[j]\) 大的素数可以由更大的 \(i\) 去筛选

Categories: LeetCode