当前位置:网站首页>【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开发日记
- 2022-2-14 learning xiangniuke project - Section 6 displays login information
- Typora installation (no need to enter serial number)
- Zzuli:1066 character classification statistics
- 使用sha256文件验证下载的文件
- PHP extensions
- Minimum value ruler method for the length of continuous subsequences whose sum is not less than s
- CNN可视化技术 -- CAM & Grad-CAM详解及pytorch简洁实现
- Regular expression summary
- 500. 键盘行
猜你喜欢
File contains vulnerability (I)
Vite打包后的dist不能直接在浏览器打开吗
Practice C language advanced address book design
GRBL 软件:简单解释的基础知识
《CGNF: CONDITIONAL GRAPH NEURAL FIELDS》阅读笔记
RNN recurrent neural network
ThreadLocal memory leak
[golang syntax] be careful with the copy of slices
3D printer G code command: complete list and tutorial
死磕大屏UI,FineReport开发日记
随机推荐
idea开发工具常用的插件合集汇总
Zzuli: maximum Convention and minimum common multiple
软件测试答疑篇
Unity Shader 学习笔记(3)URP渲染管线带阴影PBR-Shader模板(ASE优化版本)
PHP obtains some values in the string according to the specified characters, and reorganizes the remaining strings into a new array
Lambda 表达式 和 方法引用
OLED12864 液晶屏
15 C language advanced dynamic memory management
[whether PHP has soap extensions installed] a common problem for PHP to implement soap proxy: how to handle class' SoapClient 'not found in PHP
LCD之MIPI协议的一些说明
vite如何兼容低版本浏览器
Zzuli:1066 character classification statistics
492.构造矩形
Generics and generic constraints of typescript
Gcnet: non - local Networks meet Squeeze excitation Networks and Beyond
1035 Password
深度学习分类网络--VGGNet
Taskbar explicit / implicit toggle function
“簡單”的無限魔方
Thread pool overview