使用筛选法求出 n 以内的素数-Toy模板网

这篇具有很好参考价值的文章主要介绍了使用筛选法求出 n 以内的素数。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、题目介绍

输入描述：

多组输入，每行输入一个正整数（不大于100）。

输出描述：

针对每行输入的整数n，输出两行，第一行，输出n之内（包括n）的素数，用空格分隔，

第二行，输出数组中2之后被清0 的个数。每行输出后换行

二、筛选法

筛选法求解过程为：将2~n之间的正整数放在数组内存储，将数组中2之后的所有能被2整除的数清0，再将3之后的所有能被3整除的数清0 ，以此类推，直到n为止。

数组中不为0 的数即为素数。

三、解析

首先，创造一个数组，在数组内放置1~n的整数。

其次，要利用筛选法的机制，2之后的所有能被2整除的数字清0，在这里需要使用for的双层嵌套，

表示，arr[1] 需要被arr[2] ~arr[n] 的数值全部模一遍，如若出现模等于0则设置这个模arr[1]的数值变为0。文章来源地址https://www.toymoban.com/news/detail-643475.html

四、代码演示

#include <stdio.h>

int main() 
{
    int n =0;
    int count =0;
    int arr[1000];
    while(scanf("%d",&n)!=EOF)//多组输入
    {
        
        for(int i =0;i<n;i++)
        {
            arr[i]=i+1;//arr[0]内存储数字1
        }
        arr[0]=0;//把你的1拿出来不然会出错！因为任何数除去1都是整除的
        for(int i =1;i<n;i++)
        {
            if(arr[i]==0)
            {
                continue;
            }
            for(int j =i+1;j<n;j++)
    //数组中2之后的所有能被2整除的数清0，再把3之后的所有能被3整除的数字清0
            {
                if(arr[j]!=0)
                {
                    if(arr[j]%arr[i]==0)
                    {
                        arr[j]=0;
                        count++;

                    }
                }
            }
        }
        for(int i=0;i<n;i++)
        {
            if(arr[i]!=0)
            {
                printf("%d ",arr[i]);
            }
        }
        printf("\n");
        printf("%d",count);

    }
    return 0;
}

到了这里，关于使用筛选法求出 n 以内的素数的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！