【程序设计】素数（质数）

良木生香

发布于 2026-01-09 14:17:58

1460

学然后知不足，教然后知困。知不足，然后能自反也；知困，然后能自强也。

对于程序设计的题目，我们通常可以分成三个步骤来解答： 1.怎么输入 2.怎么输出 3.解题思路

要学好程序设计，就要从最基础的开始学起，那么我们今天来探讨一下，如何求素数。

题目：在屏幕上输出1~100之间的所有素数。

一、素数（质数）的定义

大于1的正整数
因数限定：只能有1和自身这两个正因数
本质属性：不可再分解为更小正整数的乘积（除 1× 自身外）

二、解题

想要完成这道题目，那就按照步骤一步一步来：

1.输入：题目只要求输出，没有输入

2.输出：输出1~100之间的质数，那么可以考虑用循环结构

3.解题思路：

既然是1~100之间的所有素数，那可以考虑用for循环：

for(int i=1;i<=100;i++)
{

}

然后就是最重要的，判断是不是质数。

根据定义，如果只有1和它本身这两个因数才叫做质数的话,那我们可以通过循环遍历从1到这个数字，看看这个区间内有没有能整除这个数字的数，如果有，那么这个数字就不是质数数，做个标记，如果没有，那就就是质数，然后输出

for (int i = 2; i <= 100; i++)   //因为1不是质数，所以从2开始遍历
{
    bool flag = 1;         //开局先假设这个数是质数
    for (int j = 2; j < i; j++)  //从2遍历到i-1，看看此区间有没有能整除数字i的数
    {
        if (i % j == 0)
        {
            flag = 0;     //如果这个数字i被区间内的j整除了，说明不是质数，用flag标记为0，表示这个数不是质数，接着退出本次循环，进入到下一个循环当中。
            break;
        }
    }
    if (flag == 1)        //加上if这个判断条件就可以知道，是由于这个i本身就是质数才来到这个语句的，而不是因为break;语句才来到这的，这样就区分了程序运行到这里时的原因
    {
        printf("%d ", i);
    }
    
}

核心的代码我们搞定了，那么现在就是全代码展示：

#include<stdio.h>
int main()
{
    for (int i = 2; i <= 100; i++)
    {
        bool flag = 1;         
        for (int j = 2; j < i; j++)  
        {
            if (i % j == 0)
            {
                flag = 0;    
                break;
            }
        }
        if (flag == 1)
        {
            printf("%d ", i);
        }
    }
    return 0;
}

现在的代码看似完美，但是再仔细看看，会发现，好像有哪里不太对劲，总觉得有哪里能优化一下，那就从第一个for循环开始找找吧。

for(int i=2;i<=100;i++)

根据质数的定义，我们可以知道，奇数虽然不一定是质数，但偶数肯定不是质数，所以，我们只需要在奇数里面寻找质数即可，那么这句代码可以修改为：

for(int i=3;i<=99;i+=2)  //从3开始遍历，每次加2，保证遍历到的都是奇数

然后再看第二个循环，能不能优化呢？包能的老铁。

根据数学知识：

所以再第二个循环当中，我们只需要循环遍历到根号i即可：

for(int i=3;i<=99;i++)
{
    for(int i=2;i<=sqrt(i);i++)   //sqrt()函数的作用是开平方，包含在<math.h>这个头文件中
    {

    }
}

根据上面的优化，我们可以写出以下代码：

#include<stdio.h>
#include<math.h>
int main()
{
    printf("%d ", 2);
    for (int i = 3; i <= 99; i+=2)
    {
        bool flag = 1;
        for (int j = 3; j <= sqrt(i); j+=2)  //也可以写成  for(int j=3;j*j<=i;j+=2)
        {
            if (i % j == 0)
            {
                flag = 0;
                break;
            }
        }
        if (flag == 1)
            printf("%d ", i);
    }
    return 0;
}

这样我们就完美的求出了1~100之间的所有素数，感兴趣的老铁可以用素数去做更多的事~~

文章是自己写的哈，有啥描述不对的、不恰当的地方，恳请大佬指正，看到后会第一时间修改，感谢您的阅读。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-10-05，如有侵权请联系 cloudcommunity@tencent.com 删除

基础