|
|
| 第1行： |
第1行： |
| ==判断单个质数==
| | #REDIRECT [[06-数学相关/01-质数判断与筛法]] |
| | | [[Category:三三文档]] |
| <math>O(\sqrt{x})</math>
| |
| | |
| <syntaxhighlight lang="cpp" line>
| |
| bool is_prime(long long x)
| |
| {
| |
| if (x < 2)
| |
| return false;
| |
| for (long long i = 2; i * i <= x; i++)
| |
| if (x % i == 0)
| |
| return false;
| |
| return true;
| |
| }
| |
| </syntaxhighlight>
| |
| | |
| ==筛法==
| |
| | |
| ===埃氏筛===
| |
| | |
| <math>O(n\log \log n)</math>
| |
| | |
| <syntaxhighlight lang="cpp" line>
| |
| const int MAXN = 10'000'000;
| |
| bool p[MAXN + 1];
| |
| //筛出 1~n 中的每个数是否为质数
| |
| void get_primes(int n)
| |
| {
| |
| //初始化
| |
| p[0] = p[1] = false;
| |
| for (int i = 2; i <= n; i++)
| |
| p[i] = true;
| |
| //筛
| |
| for (int i = 2; i <= n; i++)
| |
| if (p[i])
| |
| for (int j = i + i; j <= n; j += i)
| |
| p[j] = false;
| |
| }
| |
| </syntaxhighlight>
| |
| | |
| ===线性筛/欧拉筛===
| |
| | |
| <math>O(n)</math>
| |
| | |
| <syntaxhighlight lang="cpp" line>
| |
| const int MAXN = 10'000'000;
| |
| bool p[MAXN + 1];
| |
| vector<int> pri;
| |
| // 筛出 1~n 中的每个数是否为质数
| |
| void get_primes(int n)
| |
| {
| |
| for (int i = 1; i <= n; i++)
| |
| p[i] = true;
| |
| p[0] = p[1] = false;
| |
| for (int i = 2; i <= n; i++)
| |
| {
| |
| if (p[i])
| |
| pri.push_back(i);
| |
| for (int j = 0; j < pri.size(); j++)
| |
| {
| |
| // i*pri[j]
| |
| if (1LL * i * pri[j] > n)
| |
| break;
| |
| p[i * pri[j]] = false;
| |
| if (i % pri[j] == 0)
| |
| break;
| |
| }
| |
| }
| |
| }
| |
| </syntaxhighlight>
| |