重新理解线性筛, 推荐文章
中心思想, 每个合数都被他的最小质因数筛去。
合数 \(u = i \times p\),\(p\) 是它的最小质因数,\(u\) 是被 \(i \times p\) 筛去的,\(i\) 一定小于 \(u\),那么在算法运行到 \(u\) 之前,\(u\) 一定会被标记。
if ((i % priems[j]) == 0) break;
为什么 break
如果 i
可以被质数%成 \(0\) 那么 i = priems[j] * x;
那么对于下一个数 i * primes[j + 1]
就等价 primes[j] * x * primes[j + 1]
因为是从小到大存的质数,那么 primes[j] < primes[j + 1]
因为是用最小质因子去筛,用 primes[j + 1]
就不如 primes[j]
小(实际上这里 \(p_j\) 是 \(i\) 的最小质因子,因为从小到大排的质数,\(p_j\) 是第一个可以消掉 \(i\) 的质数, 肯定是最小质因数)所以跳过防止重复筛,并且后面的也不要了,因为我们知道可以用primes[j]
能消掉。
在筛数时 \(p <= i\)
证明:因为 \(p\) 是由 \(i\) 筛出来的,所以理论上 \(p \leq i\)。
为何在标记合数时,for (int j = 1; primes[j] <= n / i; j ++ )
不用判断 j <= cnt
:在当前已经求出了 \([1, i]\) 的质数,包含 \(i\) 的所有质因子,那么 \(i\) 总会被它含有的质因子成功取模为 \(0\),而 break
跳出循环,也就不会枚举到 \(cnt\) 之后。
线性筛 (欧拉筛) \(O(n)\)
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 1000010;int primes[N];
int n, cnt;
bool st[N];int main()
{cin >> n;for (int i = 2; i <= n; i ++ ){if (!st[i]) primes[ ++ cnt] = i; // 加入质数// primes[j] <= n / i是为了防止筛的数超过nfor (int j = 1; primes[j] <= n / i; j ++ ){st[primes[j] * i] = true; // 肯定是合数if (i % primes[j] == 0) break;}}cout << cnt << endl;return 0;
}
最后提醒一点,关于 \(n\),如果你上面循环写的是 i < n
就相当于,\(n\) 变成了 \(n - 1\),那么下面的循环就应该写 prime[j] <= (n - 1) / i
而不是 prime[j] < n / i
,这是一个容易搞错的地方,一定要知道我们的界限。
如果写成了 prime[j] < n / i
,就相当于写成了 prime <= (n / i - 1)
就相当于 prime[j] * i <= n - i
,就相当于缩小了 \(n - 1\),就会使得部分应该标记的合数,没被标记,这就导致这些合数变成了质数,就导致了我们质数筛的错误。这种错误不易发现,因此一定要注意 \(n\) 的含义,使用标准、稳定的写法。
埃氏筛 \(\operatorname O(n\log \log n)\)
算法的原理为:用每个质数,把它的倍数给筛去,而一个数可能由多个不同质数组成,所以会重复标记。
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 1000010;int primes[N];
int n, cnt;
bool st[N];int main()
{cin >> n;for (int i = 2; i <= n; i ++ ){if (!st[i]) primes[ ++ cnt] = i;else continue;for (int j = 2; j <= n / i; j ++ )st[j * i] = true;}cout << cnt << endl;return 0;
}
下面是老码风代码
线性筛 (欧拉筛) O(n)
#include<iostream>
using namespace std;
const int N=1e6+10;
int priems[N],cnt=0;
bool st[N];bool get_priems(int n)
{for (int i=2;i<=n;i++){if (!st[i]) priems[cnt++]=i;for (int j=0;priems[j]<=n/i;j++){st[priems[j]*i]=true;if ((i % priems[j]) == 0) break;}}
}
int main()
{int n;cin>>n;get_priems(n);cout<<cnt;return 0;
}
埃氏筛 O(nloglogn)约等于O(n)
#include<iostream>
using namespace std;const int N=1001001;
int priems[N],cnt;
bool st[N];
int get_priems(int n)
{for (int i=2;i <= n;i++){if (!st[i]) {priems[cnt++]=i;for (int j=i+i; j<=n;j+=i) st[j]=true;}}
}int main()
{int n;cin>>n;get_priems(n);cout<<cnt;return 0;}
```重新理解线性筛, 推荐[文章](https://zhuanlan.zhihu.com/p/100051075) 中心思想, 每个**合数**都被他的**最小质因数**筛去。合数 $u = i \times p$,$p$ 是它的最小质因数,$u$ 是被 $i \times p$ 筛去的,$i$ 一定小于 $u$,那么在算法运行到 $u$ 之前,$u$ 一定会被标记。`if ((i % priems[j]) == 0) break;` 为什么 break
如果 `i` 可以被质数%成 $0$ 那么 `i = priems[j] * x;` 那么对于下一个数 `i * primes[j + 1]` 就等价 `primes[j] * x * primes[j + 1]` 因为是从小到大存的质数,那么 `primes[j] < primes[j + 1]` 因为是用最小质因子去筛,用 `primes[j + 1]` 就不如 `primes[j]` 小(实际上这里 $p_j$ 是 $i$ 的最小质因子,因为从小到大排的质数,$p_j$ 是第一个可以消掉 $i$ 的质数, 肯定是最小质因数)所以跳过防止重复筛,并且后面的也不要了,因为我们知道可以用`primes[j]`能消掉。在筛数时 $p <= i$
证明:因为 $p$ 是由 $i$ 筛出来的,所以理论上 $p \leq i$。为何在标记合数时,`for (int j = 1; primes[j] <= n / i; j ++ )` 不用判断 `j <= cnt`:在当前已经求出了 $[1, i]$ 的质数,包含 $i$ 的所有质因子,那么 $i$ 总会被它含有的质因子成功取模为 $0$,而 `break` 跳出循环,也就不会枚举到 $cnt$ 之后。 #### 线性筛 (欧拉筛) $O(n)$```cpp
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 1000010;int primes[N];
int n, cnt;
bool st[N];int main()
{cin >> n;for (int i = 2; i <= n; i ++ ){if (!st[i]) primes[ ++ cnt] = i; // 加入质数// primes[j] <= n / i是为了防止筛的数超过nfor (int j = 1; primes[j] <= n / i; j ++ ){st[primes[j] * i] = true; // 肯定是合数if (i % primes[j] == 0) break;}}cout << cnt << endl;return 0;
}
最后提醒一点,关于 \(n\),如果你上面循环写的是 i < n
就相当于,\(n\) 变成了 \(n - 1\),那么下面的循环就应该写 prime[j] <= (n - 1) / i
而不是 prime[j] < n / i
,这是一个容易搞错的地方,一定要知道我们的界限。
如果写成了 prime[j] < n / i
,就相当于写成了 prime <= (n / i - 1)
就相当于 prime[j] * i <= n - i
,就相当于缩小了 \(n - 1\),就会使得部分应该标记的合数,没被标记,这就导致这些合数变成了质数,就导致了我们质数筛的错误。这种错误不易发现,因此一定要注意 \(n\) 的含义,使用标准、稳定的写法。
埃氏筛 \(\operatorname O(n\log \log n)\)
算法的原理为:用每个质数,把它的倍数给筛去,而一个数可能由多个不同质数组成,所以会重复标记。
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 1000010;int primes[N];
int n, cnt;
bool st[N];int main()
{cin >> n;for (int i = 2; i <= n; i ++ ){if (!st[i]) primes[ ++ cnt] = i;else continue;for (int j = 2; j <= n / i; j ++ )st[j * i] = true;}cout << cnt << endl;return 0;
}
下面是老码风代码
线性筛 (欧拉筛) O(n)
#include<iostream>
using namespace std;
const int N=1e6+10;
int priems[N],cnt=0;
bool st[N];bool get_priems(int n)
{for (int i=2;i<=n;i++){if (!st[i]) priems[cnt++]=i;for (int j=0;priems[j]<=n/i;j++){st[priems[j]*i]=true;if ((i % priems[j]) == 0) break;}}
}
int main()
{int n;cin>>n;get_priems(n);cout<<cnt;return 0;
}
埃氏筛 O(nloglogn)约等于O(n)
#include<iostream>
using namespace std;const int N=1001001;
int priems[N],cnt;
bool st[N];
int get_priems(int n)
{for (int i=2;i <= n;i++){if (!st[i]) {priems[cnt++]=i;for (int j=i+i; j<=n;j+=i) st[j]=true;}}
}int main()
{int n;cin>>n;get_priems(n);cout<<cnt;return 0;}
```重新理解线性筛, 推荐[文章](https://zhuanlan.zhihu.com/p/100051075) 中心思想, 每个**合数**都被他的**最小质因数**筛去。合数 $u = i \times p$,$p$ 是它的最小质因数,$u$ 是被 $i \times p$ 筛去的,$i$ 一定小于 $u$,那么在算法运行到 $u$ 之前,$u$ 一定会被标记。`if ((i % priems[j]) == 0) break;` 为什么 break
如果 `i` 可以被质数%成 $0$ 那么 `i = priems[j] * x;` 那么对于下一个数 `i * primes[j + 1]` 就等价 `primes[j] * x * primes[j + 1]` 因为是从小到大存的质数,那么 `primes[j] < primes[j + 1]` 因为是用最小质因子去筛,用 `primes[j + 1]` 就不如 `primes[j]` 小(实际上这里 $p_j$ 是 $i$ 的最小质因子,因为从小到大排的质数,$p_j$ 是第一个可以消掉 $i$ 的质数, 肯定是最小质因数)所以跳过防止重复筛,并且后面的也不要了,因为我们知道可以用`primes[j]`能消掉。在筛数时 $p <= i$
证明:因为 $p$ 是由 $i$ 筛出来的,所以理论上 $p \leq i$。为何在标记合数时,`for (int j = 1; primes[j] <= n / i; j ++ )` 不用判断 `j <= cnt`:在当前已经求出了 $[1, i]$ 的质数,包含 $i$ 的所有质因子,那么 $i$ 总会被它含有的质因子成功取模为 $0$,而 `break` 跳出循环,也就不会枚举到 $cnt$ 之后。 #### 线性筛 (欧拉筛) $O(n)$```cpp
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 1000010;int primes[N];
int n, cnt;
bool st[N];int main()
{cin >> n;for (int i = 2; i <= n; i ++ ){if (!st[i]) primes[ ++ cnt] = i; // 加入质数// primes[j] <= n / i是为了防止筛的数超过nfor (int j = 1; primes[j] <= n / i; j ++ ){st[primes[j] * i] = true; // 肯定是合数if (i % primes[j] == 0) break;}}cout << cnt << endl;return 0;
}
最后提醒一点,关于 \(n\),如果你上面循环写的是 i < n
就相当于,\(n\) 变成了 \(n - 1\),那么下面的循环就应该写 prime[j] <= (n - 1) / i
而不是 prime[j] < n / i
,这是一个容易搞错的地方,一定要知道我们的界限。
如果写成了 prime[j] < n / i
,就相当于写成了 prime <= (n / i - 1)
就相当于 prime[j] * i <= n - i
,就相当于缩小了 \(n - 1\),就会使得部分应该标记的合数,没被标记,这就导致这些合数变成了质数,就导致了我们质数筛的错误。这种错误不易发现,因此一定要注意 \(n\) 的含义,使用标准、稳定的写法。
埃氏筛 \(\operatorname O(n\log \log n)\)
算法的原理为:用每个质数,把它的倍数给筛去,而一个数可能由多个不同质数组成,所以会重复标记。
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 1000010;int primes[N];
int n, cnt;
bool st[N];int main()
{cin >> n;for (int i = 2; i <= n; i ++ ){if (!st[i]) primes[ ++ cnt] = i;else continue;for (int j = 2; j <= n / i; j ++ )st[j * i] = true;}cout << cnt << endl;return 0;
}
下面是老码风代码
线性筛 (欧拉筛) O(n)
#include<iostream>
using namespace std;
const int N=1e6+10;
int priems[N],cnt=0;
bool st[N];bool get_priems(int n)
{for (int i=2;i<=n;i++){if (!st[i]) priems[cnt++]=i;for (int j=0;priems[j]<=n/i;j++){st[priems[j]*i]=true;if ((i % priems[j]) == 0) break;}}
}
int main()
{int n;cin>>n;get_priems(n);cout<<cnt;return 0;
}
埃氏筛 O(nloglogn)约等于O(n)
#include<iostream>
using namespace std;const int N=1001001;
int priems[N],cnt;
bool st[N];
int get_priems(int n)
{for (int i=2;i <= n;i++){if (!st[i]) {priems[cnt++]=i;for (int j=i+i; j<=n;j+=i) st[j]=true;}}
}int main()
{int n;cin>>n;get_priems(n);cout<<cnt;return 0;}