输出200以内的素数

EMOFS • 2025-04-27 15:27 • 编程

本文将从算法原理、代码实现、优化等方面详细阐述如何输出200以内的素数。

一、算法原理

求解素数的算法有许多，比如试除法、埃氏筛法、欧拉筛法等。这里我们介绍一种简单易懂的算法——试除法。

试除法的基本思想是：对每个待判定的数，用小于它的数去除，如果不能被整除，则为素数。

根据试除法，我们可以得到200以内的素数流程如下：

int i,j;
for(i=2;i<=200;i++)
{
    for(j=2;j=i)
        printf("%d ",i);
}

代码中，外层循环i从2开始枚举200以内的数。内层循环j从2到i-1，如果存在任一j，使得i%j==0，即i能被j整除，则跳出内层循环。否则，i为素数，输出i。

二、代码实现

参考算法原理，我们可以用C语言来实现输出200以内的素数：

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

代码中，定义两个变量i和j，分别表示待判定的数和用来试除的数。i从2开始枚举，j从2到i-1，如果存在任一j，使得i%j==0，即i能被j整除，则跳出内层循环。否则，i为素数，输出i。

三、优化措施

上述代码虽然实现了输出200以内的素数，但在容量更大的情况下性能会受到影响。接下来，我们介绍几种优化措施，能够提高程序的效率。

3.1 减少重复计算

试除法中重复计算是一个比较浪费时间的地方，每次都要重复从2到i-1枚举j，计算i%j==0。当然，我们可以通过开一个数组，存储已经测试过的值，避免重复计算。数组存储后，下一次判断素数时，只需要使用已经存储的素数进行试除。

#include<stdio.h>
#define MAX 200
int main()
{
    int i,j,count=0;
    int a[MAX]={0};
    for(i=2;i<=MAX;i++)
    {
        if(a[i]==0)
        {
            printf("%d ",i);
            count++;
            for(j=i*i;j<=MAX;j+=i)
                a[j]=1;
        }
    }
    printf("\n200以内的素数数量为：%d\n",count);
    return 0;
}

代码中，定义了一个MAX常量，用于定义数组长度。利用数组实现素数的判定，数组a初始化为0，表示所有的数都是素数。从2到MAX枚举i，如果a[i]==0，表示i为素数，输出i；同时更新数组a，将i的所有倍数都标记为合数（a[j]=1）。count变量用于存储素数的数量。

3.2 减少除数的枚举范围

既然我们要判断i是否为素数，那么符合以下两个条件的数j，就不必再进行试除操作，从而减少程序的运算量。

1. j从2到i-1枚举；

2. j*j<=i。

#include<stdio.h>
#define MAX 200
int main()
{
    int i,j,count=0;
    int a[MAX]={0};
    for(i=2;i<=MAX;i++)
    {
        if(a[i]==0)
        {
            printf("%d ",i);
            count++;
            for(j=i*i;j<=MAX;j+=i)
                a[j]=1;
        }
    }
    printf("\n200以内的素数数量为：%d\n",count);
    return 0;
}

代码中，内层循环的条件变为j*j<=i，从而减少了循环次数，优化了程序的速度。

四、总结

本文介绍了输出200以内的素数的算法原理、代码实现和优化措施。试除法可以简单易懂地求解素数，但因为重复计算和循环次数过多，影响了程序效率。通过数组存储和减少除数枚举范围等优化措施，不仅提高了程序的速度，而且减少了不必要的运算。

原创文章，作者：EMOFS，如若转载，请注明出处：https://www.506064.com/n/374229.html