2025年最快求素数（质数）详解

编程基础 • 2025-09-22 09:21 • 阅读 40

我们经常会遇见一些题

要求我们判断一个数是否为素数（质数）

博主在这里讲解一种最快求素数的方法

能大量节约你的运行代码所花费的时间

废话不多说

我们先来了解一下素数的定义：

只能被常数1或自己整除，不能被其他整数整除的正整数。

我在这里先列举出100个数字里面的素数

大家先观察一下有什么规律

100里面的素数如下

2 3 5 7 11 13 17 19 23 37 41 43 47 65 67 71 73 77 79 83 85 89 91 95 97

大家可以从中看出

这些素数都在6的附近（除了2和3以外）

为什么会这样子呢？

原因：

我们在这里把所有除了前5个数的所有数

都可以看成6n 6n+1 6n+2 6n+3 6n+4 6n+5（n为正整数）

所构成的集合

那什么叫做素数呢？

素数：只能被常数1或自己整除，不能被其他整数整除的正整数。

那我们可以很快速把6n+2 6n+3 6n+4进行排除

why？

我们把这些数换一个写法大家就会豁然开朗

6*n+2=2*(3n+1)//该数可以被2整除
6*n+4=2*(3n+2)//该数可以被2整除
6*n+3=3*(2n+1)//该数可以被3整除

这些数都没有满足只能被自身和整除的条件

所有我们将他们淘汰掉

然后就剩下了6n+1和6n+5了

那是不是这样就行了呢？

其实不然

在满足在6附近数也可能存在不是素数的数

例如25 35 49

他们可能被6n+1和6n+5整除

为什么呢

因为6n+2,6n+4他们一定是2的倍数

而6n+3一定是3的倍数

但6n+1和6n+5不能被2和3整除

故6n+1和6n+5只可能被6m+1和6m+5整除（m<=n）

我们就可以从6周围的数一直加6

一直加到我们要求素数的平方根

（要是能被平方根整除，那他也不是素数）

观察我们要判断的数是否能够被他们整除

最后排除所有的不是素数的可能

那么心机之蛙一直摸你肚子

他就是素数！！！

好，不皮了样例代码如下

#include<stdio.h>
#include<math.h>//求平方根的头文件
#include<iostream>
using namespace std;
bool sushu(int nb)//bool函数，只会返回真(true)[不等于0]或者假(false)[等于0]
{
    if (nb == 2 || nb == 3)//先判断小于5的素数
        return true;//返回真
    if (nb % 6 != 5 && nb % 6 != 1)//去掉不在6周围的情况
        return false;
    int cmb = (int)sqrt(nb);//强制转换成int型，返回值问题详细可见我的另外一篇博客
    for (int i = 5; i <= cmb; i += 6)
    {
        if (nb % i == 0||nb%(i+2)==0)
            return false;//返回假
    }
    return true;//去掉所有不满足的情况，就是满足的情况
}
int main()
{
    for (int n = 2; n <= 100; n++)
        if (sushu(n))
            cout << n << " ";
    return 0;
}

PS:sqrt与pow返回类型详解

sqrt 和pow 的返回值类型错误（{从小白开始c语言常见错误归纳第2弹）_代码changeword的博客-CSDN博客

PS:人生就是一场游戏，而真正的成功永远不是一蹴而就，做好每一处细节，你才是最后的winner，加油，敲代码的同学们。

2025年最快求素数（质数）详解

相关推荐