质数判断：修订间差异

来自三三百科
跳转到导航 跳转到搜索
33DAI​（留言 | 贡献）
行政员、​界面管理员、​管理员
216次编辑
可视化wikitext
33DAI​（留言 | 贡献）
行政员、​界面管理员、​管理员
216次编辑
创建页面，内容为“==判断单个质数== <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 中的每个数是否为质数…”
 
33DAI​（留言 | 贡献）
行政员、​界面管理员、​管理员
216次编辑
批量导入三三文档
标签：新重定向
 
（未显示同一用户的1个中间版本）
第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 (i * pri[j] > n)
                break;
            p[i * pri[j]] = false;
            if (i % pri[j] == 0)
                break;
        }
    }
}
</syntaxhighlight>

2026年5月20日 (三) 18:24的最新版本

重定向到：

检索自“https://www.33dai.wiki/index.php?title=质数判断&oldid=460”