题目描述
给定整数 n ，返回 所有小于非负整数 n 的质数的数量 。
示例 1：
输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
示例 2：
输入：n = 0
输出：0
示例 3：
输入：n = 1
输出：0
题解
思路1:暴力枚举
质数的定义 在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数
对于每个数x，在[2,x-1]的区间内，如果存在y是x的因数，那么x就不是质数，否则为质数
如果存在y是x的因数（即x%y==0），那么x/y也是x的因数，因而我们只需校验y或者x/y即可，每次我们校验y和y/x中的较小值，那么y<=x/y,则y的范围为[2,√x]
// OC
+ (int)countPrimes1:(int)n {
if (n<2) {
return 0;
}
int ans = 0;
for (int i=2; i<n; i++) {
if ([self isPrimes1:i]) {
ans += 1;
}
}
return ans;
}
+ (BOOL)isPrimes1:(int)n {
int i=2;
double end = sqrt(n);
while (i<=end) {
if (n%i==0) {
return NO;
}
i++;
}
return YES;
}
// Swift
// 质数的定义 在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数
// 对于每个数x，在[2,x-1]的区间内，如果存在y是x的因数，那么x就不是质数，否则为质数
// 如果存在y是x的因数（即x%y==0），那么x/y也是x的因数，因而我们只需校验y或者x/y即可，每次我们校验y和y/x中的较小值，那么y<=x/y,则y的范围为[2,√x]
static public func countPrimes1(_ n:Int) -> Int {
if (n<2) {return 0}
var ans = 0
for i in 2..<n {
if isPrimes1(i) {
ans += 1
}
}
return ans
}
static func isPrimes1(_ n:Int) -> Bool {
var i = 2
let end = Int(sqrt(Double(n)))
while i<=end {
if n%i == 0 {
return false
}
i+=1
}
return true
}
思路2: 埃氏筛
如果x 是质数，那么大于x的倍数（2x,3x,..）一定都是合数
对于一个质数 x，如果按上文说的我们从2x开始标记其实是冗余的，应该直接从 x*x 开始标记，因为 2x,3x,…这些数一定在 x之前就被其他数的倍数标记过了，例如 2的所有倍数，3 的所有倍数等，
对于质数x，合数nx<xx,n<x,如果n为质数，那么在之前的遍历到n时，nx一定会被标记，如果n为合数，那么一定存在一个质数j(合数一定有质因数)，n=j * n/j，由于n<x,那么j<x,那么在之前的遍历到j时，nx也一定会被标记，因而可以从xx开始标记
对于任意数x，如果x是合数，那么一定存在最小质因子j，在遍历到x前(即遍历j时)，将x标记为合数
如果x为质数，那么在之前的遍历中，一定不会将x标记为合数，因而此时遍历到x时，x还是质数
综上
任何一个合数,都可以写成两个或者两个以上的质数相乘的形式
对于任意数x，假设x为质数，那么不存在质数j，使得j * x/j=x,那么在x之前的遍历中，不会将x标记为合数
假设x为合数，那么存在两个以上的质数，使得x=j0 * j1 * j2...jn(j0<=j1<=...jn)，那么在之前遍历质数j0时，一定存在n(n=j1 * j2 *...jn),n>=j0,使得x=n * j0>= j0 * j0,那么x在遍历质数j0时就会被标记为合数，又由于n>=j0,那么从j0 * j0开始遍历，也可以遍历到x，将x标记为合数
// OC
+ (int)countPrimes2:(int)n {
if (n<2) {
return 0;
}
int ans = 0;
NSMutableArray *primeFlagArray = [[NSMutableArray alloc] init];
for (int i=0; i<n; i++) {
[primeFlagArray addObject:@1];
}
for (int i=2; i<n; i++) {
if ([primeFlagArray[i] intValue] == 1) {
ans += 1;
int j=i;
// 将所有j*i都标记为合数，j从i开始
while (j*i<n) {
primeFlagArray[j*i] = @0;
j+=1;
}
}
}
return ans;
}
// Swift
// 如果x 是质数，那么大于x的倍数（2x,3x,..）一定都是合数
// 对于一个质数 x，如果按上文说的我们从2x开始标记其实是冗余的，应该直接从 x⋅x 开始标记，因为 2x,3x,…这些数一定在 x之前就被其他数的倍数标记过了，例如 2 的所有倍数，3 的所有倍数等，
// 合数一定有质因数，对于质数x，合数nx<x*x,n<x,如果n为质数，那么在之前的遍历到n时，nx一定会被标记，如果n为合数，那么一定存在一个质数j，n=j*n/j，由于n<x,那么j<x,那么在之前的遍历到j时，nx也一定会被标记，因而可以从x*x开始标记
// 对于任意数x，如果x是合数，那么一定存在最小质因子j，在遍历到x前(即遍历j时)，将x标记为合数
// 如果x为质数，那么在之前的遍历中，一定不会将x标记为合数，因而此时遍历到x时，x还是质数
/*
任何一个合数,都可以写成两个或者两个以上的质数相乘的形式
对于任意数x，假设x为质数，那么不存在质数j，使得j*x/j=x,那么在x之前的遍历中，不会将x标记为合数
假设x为合数，那么存在两个以上的质数，使得x=j0 * j1 *...jn(j0<=j1<=..jn)，那么在之前遍历质数j0时，一定存在n(n=j1*..jn),n>=j0,使得x=n*j0>=j0*j0,那么x在遍历质数j0时就会被标记为合数，又由于
n>=j0,那么从j0*j0开始遍历，也可以遍历到x，将x标记为合数
*/
static public func countPrimes2(_ n:Int) -> Int {
if (n<2) {return 0}
var ans = 0
var primesFlagArray = Array(repeating: true, count: n)
for i in 2..<n {
if primesFlagArray[i] {
ans += 1
for j in stride(from: i*i, to: n, by: i) {
primesFlagArray[j] = false
}
}
}
return ans
}
思路3: 线性筛
埃氏筛其实还是存在冗余的标记操作，比如对于 45 这个数，它会同时被 3,5 两个数标记为合数，因此我们优化的目标是让每个合数只被标记一次，这样时间复杂度即能保证为 O(n)，这就是我们接下来要介绍的线性筛。
相较于埃氏筛，我们多维护一个 primes 数组表示当前得到的质数集合。我们从小到大遍历，如果当前的数 x 是质数，就将其加入 primes 数组。
另一点与埃氏筛不同的是，「标记过程」不再仅当 x 为质数时才进行，而是对每个整数 x 都进行。对于整数 x，我们不再标记其所有的倍数 xx,x(x+1),…，而是只标记质数集合中的数与 x 相乘的数，即 x * primes(0),x * primes(1),…,且在发现 x%primes(i)==0时结束当前标记
核心点在于：如果x可以被 primes(i)整除，那么对于合数 y=x * primes(i+1)而言，它一定在后面遍历到x/primes(i) * primes(i+1) 这个数的时候会被标记，其他同理，这保证了每个合数只会被其「最小的质因数」筛去，即每个合数被标记一次
先不管 x%primes(i)==0时结束当前标记
对于任意数x，如果x为质数，那么x一定不会被标记为合数的
如果x为合数，那么一定存在两个以上的质数，使得x=j0 * j1 * j2..jn(j0<=j1<=j2..jn),即存在a=j1 * j2..jn,即x=a * j0(a>=j0)，由于a>=j0,那么遍历到a时，j0已加入到primes中，遍历primes时，会将x=a * j0标记为合数
现在来看下为什么x%primes(i)==0时结束当前标记，对于合数y=x * primes(i+1),会在后续遍历中标记
对于x%primes(i)==0,且primes数组中存在primes(i+1),primes(i+1)>primes(i),那么x一定为合数，如果x为质数，x%primes(i)==0,primes(i)=x,而primes(i+1)>primes(i)即primes(i+1)>x,此时primes(i+1)还未遍历到，因而x为合数，对于合数，一定存在两个以上的质因子，使得x=j0 * j1 * ..jn,又由于标记循环是从小到大的，那么primes(i)是x的最小质因子，即j0,那么对于y=x * primes(i+1),y=j0 * j1 * ..jn * primes(i+1),又由于primes(i+1)>j0,那么后续遍历中存在z=j1 * ..jn * primes(i+1) (z>x),在遍历z时，将y标记为合数
// OC
+ (int)countPrimes3:(int)n {
if (n<2) {
return 0;
}
// 存储质数
NSMutableArray *primesArray = [[NSMutableArray alloc] init];
// 先全部标记为质数
NSMutableArray *primeFlagArray = [[NSMutableArray alloc] init];
for (int i=0; i<n; i++) {
[primeFlagArray addObject:@1];
}
for (int i=2; i<n; i++) {
if ([primeFlagArray[i] intValue] == 1) {
[primesArray addObject:[NSNumber numberWithInt:i]];
}
int j=0;
// 将i*primesArray[j] 全部标记为合数
while ([primesArray[j] intValue] * i < n && j<primesArray.count) {
primeFlagArray[[primesArray[j] intValue] * i] = @0;
// 当i%primesArray[j]==0时，退出j循环，i*primesArray[j+1]的数会在后面的循环中标记的
if (i % [primesArray[j] intValue] == 0) {
break;
}
j += 1;
}
}
return (int)primesArray.count;
}
// Swift
// 埃氏筛其实还是存在冗余的标记操作，比如对于 45 这个数，它会同时被 3,5 两个数标记为合数，因此我们优化的目标是让每个合数只被标记一次，这样时间复杂度即能保证为 O(n)，这就是我们接下来要介绍的线性筛。
// 相较于埃氏筛，我们多维护一个 primes 数组表示当前得到的质数集合。我们从小到大遍历，如果当前的数 x 是质数，就将其加入 primes 数组。
// 另一点与埃氏筛不同的是，「标记过程」不再仅当 x 为质数时才进行，而是对每个整数 x 都进行。对于整数 x，我们不再标记其所有的倍数 x*x,x*(x+1),…，而是只标记质数集合中的数与 x 相乘的数，即 x*primes(0),x*primes(1),…,且在发现 x%primes(i)==0时结束当前标记
// 核心点在于：如果x可以被 primes(i)整除，那么对于合数 y=x*primes(i+1)而言，它一定在后面遍历到x/primes(i)*primes(i+1) 这个数的时候会被标记，其他同理，这保证了每个合数只会被其「最小的质因数」筛去，即每个合数被标记一次
// 先不管 x%primes(i)==0时结束当前标记
// 对于任意数x，如果x为质数，那么x一定不会被标记为合数的
// 如果x为合数，那么一定存在两个以上的质数，使得x=j0*j1*j2..jn(j0<=j1<=j2..jn),即存在a=j1*j2..jn,即x=a*j0(a>=j0)，由于a>=j0,那么遍历到a时，j0已加入到primes中，遍历primes时，会将x=a*j0标记为合数
// 现在来看下为什么x%primes(i)==0时结束当前标记，对于合数y=x*primes(i+1),会在后续遍历中标记
// 对于x%primes(i)==0,且primes数组中存在primes(i+1),primes(i+1)>primes(i),那么x一定为合数，如果x为质数，x%primes(i)==0,primes(i)=x,而primes(i+1)>primes(i)即primes(i+1)>x,此时primes(i+1)还未遍历到，因而x为合数，对于合数，一定存在两个以上的质因子，使得x=j0*j1*..jn,又由于标记循环是从小到大的，那么primes(i)是x的最小质因子，即j0,那么对于y=x*primes(i+1),y=j0*j1*..jn*primes(i+1),又由于primes(i+1)>j0,那么后续遍历中存在z=j1*..jn*primes(i+1) (z>x),在遍历z时，将y标记为合数
static public func countPrimes3(_ n:Int) -> Int {
if (n<2) {return 0}
var primesFlagArray = Array(repeating: true, count: n)
var primesArray = [Int]()
for i in 2..<n {
if primesFlagArray[i] {
primesArray.append(i)
}
var j = 0
while(j<primesArray.count && primesArray[j]*i<n) {
primesFlagArray[primesArray[j]*i] = false
if i%primesArray[j] == 0 {
break
}
j+=1
}
}
return primesArray.count
}
参考：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnzlu6/
https://leetcode-cn.com/problems/count-primes/solution/ji-shu-zhi-shu-by-leetcode-solution/
