題目描述
給定整數(shù) n ，返回 所有小于非負(fù)整數(shù) n 的質(zhì)數(shù)的數(shù)量 。
示例 1：
輸入：n = 10
輸出：4
解釋：小于 10 的質(zhì)數(shù)一共有 4 個, 它們是 2, 3, 5, 7 。
示例 2：
輸入：n = 0
輸出：0
示例 3：
輸入：n = 1
輸出：0
題解
思路1:暴力枚舉
質(zhì)數(shù)的定義 在大于1的自然數(shù)中，除了1和它本身以外不再有其他因數(shù)的自然數(shù)
對于每個數(shù)x，在[2,x-1]的區(qū)間內(nèi)，如果存在y是x的因數(shù)，那么x就不是質(zhì)數(shù)，否則為質(zhì)數(shù)
如果存在y是x的因數(shù)（即x%y==0），那么x/y也是x的因數(shù)，因而我們只需校驗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
// 質(zhì)數(shù)的定義 在大于1的自然數(shù)中，除了1和它本身以外不再有其他因數(shù)的自然數(shù)
// 對于每個數(shù)x，在[2,x-1]的區(qū)間內(nèi)，如果存在y是x的因數(shù)，那么x就不是質(zhì)數(shù)，否則為質(zhì)數(shù)
// 如果存在y是x的因數(shù)（即x%y==0），那么x/y也是x的因數(shù)，因而我們只需校驗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 是質(zhì)數(shù)，那么大于x的倍數(shù)（2x,3x,..）一定都是合數(shù)
對于一個質(zhì)數(shù) x，如果按上文說的我們從2x開始標(biāo)記其實是冗余的，應(yīng)該直接從 x*x 開始標(biāo)記，因為 2x,3x,…這些數(shù)一定在 x之前就被其他數(shù)的倍數(shù)標(biāo)記過了，例如 2的所有倍數(shù)，3 的所有倍數(shù)等，
對于質(zhì)數(shù)x，合數(shù)nx<xx,n<x,如果n為質(zhì)數(shù)，那么在之前的遍歷到n時，nx一定會被標(biāo)記，如果n為合數(shù)，那么一定存在一個質(zhì)數(shù)j(合數(shù)一定有質(zhì)因數(shù))，n=j * n/j，由于n<x,那么j<x,那么在之前的遍歷到j(luò)時，nx也一定會被標(biāo)記，因而可以從xx開始標(biāo)記
對于任意數(shù)x，如果x是合數(shù)，那么一定存在最小質(zhì)因子j，在遍歷到x前(即遍歷j時)，將x標(biāo)記為合數(shù)
如果x為質(zhì)數(shù)，那么在之前的遍歷中，一定不會將x標(biāo)記為合數(shù)，因而此時遍歷到x時，x還是質(zhì)數(shù)
綜上
任何一個合數(shù),都可以寫成兩個或者兩個以上的質(zhì)數(shù)相乘的形式
對于任意數(shù)x，假設(shè)x為質(zhì)數(shù)，那么不存在質(zhì)數(shù)j，使得j * x/j=x,那么在x之前的遍歷中，不會將x標(biāo)記為合數(shù)
假設(shè)x為合數(shù)，那么存在兩個以上的質(zhì)數(shù)，使得x=j0 * j1 * j2...jn(j0<=j1<=...jn)，那么在之前遍歷質(zhì)數(shù)j0時，一定存在n(n=j1 * j2 *...jn),n>=j0,使得x=n * j0>= j0 * j0,那么x在遍歷質(zhì)數(shù)j0時就會被標(biāo)記為合數(shù)，又由于n>=j0,那么從j0 * j0開始遍歷，也可以遍歷到x，將x標(biāo)記為合數(shù)
// 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都標(biāo)記為合數(shù)，j從i開始
while (j*i<n) {
primeFlagArray[j*i] = @0;
j+=1;
}
}
}
return ans;
}
// Swift
// 如果x 是質(zhì)數(shù)，那么大于x的倍數(shù)（2x,3x,..）一定都是合數(shù)
// 對于一個質(zhì)數(shù) x，如果按上文說的我們從2x開始標(biāo)記其實是冗余的，應(yīng)該直接從 x?x 開始標(biāo)記，因為 2x,3x,…這些數(shù)一定在 x之前就被其他數(shù)的倍數(shù)標(biāo)記過了，例如 2 的所有倍數(shù)，3 的所有倍數(shù)等，
// 合數(shù)一定有質(zhì)因數(shù)，對于質(zhì)數(shù)x，合數(shù)nx<x*x,n<x,如果n為質(zhì)數(shù)，那么在之前的遍歷到n時，nx一定會被標(biāo)記，如果n為合數(shù)，那么一定存在一個質(zhì)數(shù)j，n=j*n/j，由于n<x,那么j<x,那么在之前的遍歷到j(luò)時，nx也一定會被標(biāo)記，因而可以從x*x開始標(biāo)記
// 對于任意數(shù)x，如果x是合數(shù)，那么一定存在最小質(zhì)因子j，在遍歷到x前(即遍歷j時)，將x標(biāo)記為合數(shù)
// 如果x為質(zhì)數(shù)，那么在之前的遍歷中，一定不會將x標(biāo)記為合數(shù)，因而此時遍歷到x時，x還是質(zhì)數(shù)
/*
任何一個合數(shù),都可以寫成兩個或者兩個以上的質(zhì)數(shù)相乘的形式
對于任意數(shù)x，假設(shè)x為質(zhì)數(shù)，那么不存在質(zhì)數(shù)j，使得j*x/j=x,那么在x之前的遍歷中，不會將x標(biāo)記為合數(shù)
假設(shè)x為合數(shù)，那么存在兩個以上的質(zhì)數(shù)，使得x=j0 * j1 *...jn(j0<=j1<=..jn)，那么在之前遍歷質(zhì)數(shù)j0時，一定存在n(n=j1*..jn),n>=j0,使得x=n*j0>=j0*j0,那么x在遍歷質(zhì)數(shù)j0時就會被標(biāo)記為合數(shù)，又由于
n>=j0,那么從j0*j0開始遍歷，也可以遍歷到x，將x標(biāo)記為合數(shù)
*/
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: 線性篩
埃氏篩其實還是存在冗余的標(biāo)記操作，比如對于 45 這個數(shù)，它會同時被 3,5 兩個數(shù)標(biāo)記為合數(shù)，因此我們優(yōu)化的目標(biāo)是讓每個合數(shù)只被標(biāo)記一次，這樣時間復(fù)雜度即能保證為 O(n)，這就是我們接下來要介紹的線性篩。
相較于埃氏篩，我們多維護(hù)一個 primes 數(shù)組表示當(dāng)前得到的質(zhì)數(shù)集合。我們從小到大遍歷，如果當(dāng)前的數(shù) x 是質(zhì)數(shù)，就將其加入 primes 數(shù)組。
另一點與埃氏篩不同的是，「標(biāo)記過程」不再僅當(dāng) x 為質(zhì)數(shù)時才進(jìn)行，而是對每個整數(shù) x 都進(jìn)行。對于整數(shù) x，我們不再標(biāo)記其所有的倍數(shù) xx,x(x+1),…，而是只標(biāo)記質(zhì)數(shù)集合中的數(shù)與 x 相乘的數(shù)，即 x * primes(0),x * primes(1),…,且在發(fā)現(xiàn) x%primes(i)==0時結(jié)束當(dāng)前標(biāo)記
核心點在于：如果x可以被 primes(i)整除，那么對于合數(shù) y=x * primes(i+1)而言，它一定在后面遍歷到x/primes(i) * primes(i+1) 這個數(shù)的時候會被標(biāo)記，其他同理，這保證了每個合數(shù)只會被其「最小的質(zhì)因數(shù)」篩去，即每個合數(shù)被標(biāo)記一次
先不管 x%primes(i)==0時結(jié)束當(dāng)前標(biāo)記
對于任意數(shù)x，如果x為質(zhì)數(shù)，那么x一定不會被標(biāo)記為合數(shù)的
如果x為合數(shù)，那么一定存在兩個以上的質(zhì)數(shù)，使得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標(biāo)記為合數(shù)
現(xiàn)在來看下為什么x%primes(i)==0時結(jié)束當(dāng)前標(biāo)記，對于合數(shù)y=x * primes(i+1),會在后續(xù)遍歷中標(biāo)記
對于x%primes(i)==0,且primes數(shù)組中存在primes(i+1),primes(i+1)>primes(i),那么x一定為合數(shù)，如果x為質(zhì)數(shù)，x%primes(i)==0,primes(i)=x,而primes(i+1)>primes(i)即primes(i+1)>x,此時primes(i+1)還未遍歷到，因而x為合數(shù)，對于合數(shù)，一定存在兩個以上的質(zhì)因子，使得x=j0 * j1 * ..jn,又由于標(biāo)記循環(huán)是從小到大的，那么primes(i)是x的最小質(zhì)因子，即j0,那么對于y=x * primes(i+1),y=j0 * j1 * ..jn * primes(i+1),又由于primes(i+1)>j0,那么后續(xù)遍歷中存在z=j1 * ..jn * primes(i+1) (z>x),在遍歷z時，將y標(biāo)記為合數(shù)
// OC
+ (int)countPrimes3:(int)n {
if (n<2) {
return 0;
}
// 存儲質(zhì)數(shù)
NSMutableArray *primesArray = [[NSMutableArray alloc] init];
// 先全部標(biāo)記為質(zhì)數(shù)
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] 全部標(biāo)記為合數(shù)
while ([primesArray[j] intValue] * i < n && j<primesArray.count) {
primeFlagArray[[primesArray[j] intValue] * i] = @0;
// 當(dāng)i%primesArray[j]==0時，退出j循環(huán)，i*primesArray[j+1]的數(shù)會在后面的循環(huán)中標(biāo)記的
if (i % [primesArray[j] intValue] == 0) {
break;
}
j += 1;
}
}
return (int)primesArray.count;
}
// Swift
// 埃氏篩其實還是存在冗余的標(biāo)記操作，比如對于 45 這個數(shù)，它會同時被 3,5 兩個數(shù)標(biāo)記為合數(shù)，因此我們優(yōu)化的目標(biāo)是讓每個合數(shù)只被標(biāo)記一次，這樣時間復(fù)雜度即能保證為 O(n)，這就是我們接下來要介紹的線性篩。
// 相較于埃氏篩，我們多維護(hù)一個 primes 數(shù)組表示當(dāng)前得到的質(zhì)數(shù)集合。我們從小到大遍歷，如果當(dāng)前的數(shù) x 是質(zhì)數(shù)，就將其加入 primes 數(shù)組。
// 另一點與埃氏篩不同的是，「標(biāo)記過程」不再僅當(dāng) x 為質(zhì)數(shù)時才進(jìn)行，而是對每個整數(shù) x 都進(jìn)行。對于整數(shù) x，我們不再標(biāo)記其所有的倍數(shù) x*x,x*(x+1),…，而是只標(biāo)記質(zhì)數(shù)集合中的數(shù)與 x 相乘的數(shù)，即 x*primes(0),x*primes(1),…,且在發(fā)現(xiàn) x%primes(i)==0時結(jié)束當(dāng)前標(biāo)記
// 核心點在于：如果x可以被 primes(i)整除，那么對于合數(shù) y=x*primes(i+1)而言，它一定在后面遍歷到x/primes(i)*primes(i+1) 這個數(shù)的時候會被標(biāo)記，其他同理，這保證了每個合數(shù)只會被其「最小的質(zhì)因數(shù)」篩去，即每個合數(shù)被標(biāo)記一次
// 先不管 x%primes(i)==0時結(jié)束當(dāng)前標(biāo)記
// 對于任意數(shù)x，如果x為質(zhì)數(shù)，那么x一定不會被標(biāo)記為合數(shù)的
// 如果x為合數(shù)，那么一定存在兩個以上的質(zhì)數(shù)，使得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標(biāo)記為合數(shù)
// 現(xiàn)在來看下為什么x%primes(i)==0時結(jié)束當(dāng)前標(biāo)記，對于合數(shù)y=x*primes(i+1),會在后續(xù)遍歷中標(biāo)記
// 對于x%primes(i)==0,且primes數(shù)組中存在primes(i+1),primes(i+1)>primes(i),那么x一定為合數(shù)，如果x為質(zhì)數(shù)，x%primes(i)==0,primes(i)=x,而primes(i+1)>primes(i)即primes(i+1)>x,此時primes(i+1)還未遍歷到，因而x為合數(shù)，對于合數(shù)，一定存在兩個以上的質(zhì)因子，使得x=j0*j1*..jn,又由于標(biāo)記循環(huán)是從小到大的，那么primes(i)是x的最小質(zhì)因子，即j0,那么對于y=x*primes(i+1),y=j0*j1*..jn*primes(i+1),又由于primes(i+1)>j0,那么后續(xù)遍歷中存在z=j1*..jn*primes(i+1) (z>x),在遍歷z時，將y標(biāo)記為合數(shù)
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/
