当前位置:网站首页>【C语言】筛选法求素数
【C语言】筛选法求素数
2022-07-02 05:52:00 【SouLinya】
题目
描述
用筛选法求n以内的素数。筛选法求解过程为:将2~n之间的正整数放在数组内存储,将数组中2之后的所有能被2整除的数清0,再将3之后的所有能被3整除的数清0 ,以此类推,直到n为止。数组中不为0 的数即为素数。
输入描述
多组输入,每行输入一个正整数(不大于100)。
输出描述
针对每行输入的整数n,输出两行,第一行,输出n之内(包括n)的素数,用空格分隔
示例
输入:20
输出:
2 3 5 7 11 13 17 19
11
一、思路
常见的求判断素数的方法有试除法,还有就是用sqrt或1/2。筛选法与试除法相似,每个数都要除以除1和它本身之外的数进行判断。筛选法的关键在于:(1)要求将2-n的数字先存入数组中;(2)在将2之后的,注意是2之后的数字能被2整除的清零,然后向后移一位,从3开始,在将3之后的能被3整除的清零,依次类推,直到n。简单说就是最开始指向的是数组的2后3,一轮循环遍历除以2后,数组最开始指向的位置向后偏1,指向数组3后的4,考虑如何平衡循环i和j的值。
二、代码实现
#include<stdio.h>
int main()
{
int n;
int count=0;
int arr[100]={
0};
while(scanf("%d",&n)!=EOF)
{
int j=0;
int i=0;
for(i=2;i<=n;i++)
{
arr[j++]=i;//赋值
//arr[0]=2,arr[1]=3...arr[18]=20
}
//清零
for(i=2;i<=n;i++)//除数的变化
{
for(j=i-1;j<n-1;j++)//被除数的变化
{
//开头的数是+1变化的,所以我们利用i
if(arr[j]%i==0)
{
arr[j]=0;
}
}
}
//打印
//由于会多初始化一个数,所以i<n-1
for(i=0;i<n-1;i++)
{
if(arr[i]!=0)
{
count++;
printf("%d ",arr[i]);
}
}
printf("\n%d\n",n-1-count);
}
return 0;
}
边栏推荐
猜你喜欢
死磕大屏UI,FineReport开发日记
Brew install * failed, solution
Oled12864 LCD screen
Appnuim environment configuration and basic knowledge
Practice C language advanced address book design
Test case
Gcnet: non - local Networks meet Squeeze excitation Networks and Beyond
Alibaba: open source and self-developed liquid cooling data center technology
OLED12864 液晶屏
2022-2-14 learning xiangniuke project - section 23, section 5, development login and exit functions
随机推荐
1036 Boys vs Girls
[PHP是否安装了 SOAP 扩]对于php实现soap代理的一个常见问题:Class ‘SoapClient‘ not found in PHP的处理方法
Alibaba: open source and self-developed liquid cooling data center technology
3D 打印机 G 代码命令:完整列表和教程
[paper translation] gcnet: non local networks meet squeeze exception networks and beyond
图片裁剪插件cropper.js
I want to understand the swift code before I learn it. I understand it
[personal test] copy and paste code between VirtualBox virtual machine and local
php数组转化为xml
Common protocols and download paths of NR
PHP extensions
idea开发工具常用的插件合集汇总
js判断移动端还是pc端
Zzuli:1060 numbers in reverse order
Fundamentals of software testing
PHP read file (read JSON file, convert to array)
[technical notes-08]
500. 键盘行
Visual studio import
How to write good code - Defensive Programming Guide