杨晨旭

用户名：dotcpp0598807

访问量：5054

签　名：

等　　级
排　　名	6642
经　　验	1396
参赛次数	0
文章发表	2
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

明明的随机数
浏览：131

你可能喜欢

筛选N以内的素数

　　作者: 杨晨旭　　　　发表时间：2022-09-20 00:02:16 浏览：4820　|　评论：6　

原题链接：[编程入门]筛选N以内的素数

## 思路一

素数（质数）是指除了 1 和它本身以外，不能被任何整数整除的数，例如`7`就是素数，因为它不能被` 2~6 `的任一整数整除。

所以我们可以判断一个整数m是否是素数，只需把` i  `被 `2 ~i -1` 之间的每一个整数去除，如果都不能被整除，那么 ` i ` 就是一个素数。

## 思路二

我们可以从合数角度来看

如果` i `能被 `2 ~ i-1 `之间任一整数整除，那么两个因子中必定有一个小于或等于 $$ \sqrt{i} $$  ，另一个大于或等于$$ \sqrt{i} $$。

这样我们只需要在`2 ~$$ \sqrt{i} $$`之间判断，如果能在`2 ~ $$ \sqrt{i} $$`被整除，那么他就不是素数。这样我们可以减少循环次数。
## 思路三

与思路二同理但是不需要math头文件，只需要折半模除判断，即判断`i~i/2 `

----
### 思路一 源代码
```c
#include <stdio.h>
int main()
{
    int SuShu_Panduan();
    int N,i=2;
    scanf("%d",&N);
    for(;i<=N;i++)
    {
        SuShu_Panduan(i);
    }
    return 0;
}

int SuShu_Panduan(int i)
{
    int tag=0;  //c中没有bool类型 使用0 1代替
    for(int m=2;m<i;m++)   // m<i 即 m<=i-1   从2~i-1
    {
        if(i%m==0)
        {
            tag++;
        }
    }
    if(tag==0)
    printf("%d\n", i);
    return 0;
}
```
---
运行时内存占用：
![](/image_editor_upload/20220919/20220919115207_71610.jpg)
###思路二 源代码
```c
#include <stdio.h>
#include<math.h> //添加math库
int main()
{
    int SuShu_Panduan();
    int N,i=2;
    scanf("%d",&N);
    for(;i<=N;i++)
    {
        SuShu_Panduan(i);
    }
    return 0;
}

int SuShu_Panduan(int i)
{
    int tag=0;  //c中没有bool类型 使用0 1代替
    for(int m=2;m<sqrt(i);m++) //调用sqrt函数
    {
        if(i%m==0){
            tag++;
        }
    }
    if(tag==0)
    printf("%d\n", i);
    return 0;
}
```
---
运行时内存占用：
![](/image_editor_upload/20220919/20220919115131_21995.jpg)
### 思路三 源代码

```c
#include <stdio.h>
int main()
{
    int SuShu_Panduan();
    int N,i=2;
    scanf("%d",&N);
    for(;i<=N;i++)
    {
        SuShu_Panduan(i);
    }
    return 0;
}

int SuShu_Panduan(int i)
{
    int tag=0; //c中没有bool类型 使用0 1代替
    for(int m=2;m<i/2;m++)  // 改变此处
    {
        if(i%m==0){
            tag++;
        }
    }
    if(tag==0)
    printf("%d\n", i);
    return 0;
}
```
---
运行时内存占用：
![](/image_editor_upload/20220920/20220920120007_84955.jpg)

内存大差不差，随便写写，记录一下无聊时候在干什么。

0.0分

21 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

ccc

int main()
{
	int a;
	int i = 2, b = 1, c =0;
	scanf("%d", &a);
	printf("%d\n",2);
	for (i ; i < a ; i++)
	{
		b = 1;
		while (b < i-1)
		{
			b++;
			if (i % b == 0)
			{
				break;
			}
		}
		if (i % b != 0)
		{
			printf("%d\n", i);
		}
	}
	return 0;
}
让我来

2023-12-07 21:32:24

dot666 2023-12-10 20:42:34 |

你这个确实不错

macy 2023-12-27 12:46:17 |

2不是计算机算的吧，不是你自己输入的么。这个不是判断得来的

macy 2023-12-27 12:50:34 |

#include<stdio.h> int main() { int N; scanf_s("%d", &N); int i,b; printf("2\n"); for (i = 2;i <= N;i++) { for (b = 1;b < i - 1;) { b++; if (i % b == 0) { break; } } if (i % b != 0) printf("%d\n", i); } return 0; }

macy 2023-12-27 12:50:50 |

黄小橘

#include<stdio.h>
#include<math.h>
int main()
{
    int i,n,j,k;
    scanf("%d",&n);
    for(i=2;i<=n;i++)
    {
    	int s=1;
    	for(j=2;j<i;j++)
    	{
    		if(i%j==0) 
    		s=0;
    	}
    	if(s) printf("%d  ",i);
    }
    return 0;
}

2023-11-22 22:02:53

漱石

思路三当i==4的时候就错了，m<i/2不成立直接跳出循环，printf了4

2023-04-28 19:48:33

ljq1417

思路一运行错误啊，说提供给函数的参数过多

2023-02-01 11:28:26

StarHui

第二个代码有点问题，应该是m <= sqrt(i),没有考虑到可以被开平方的情况，比如36、49这样的情况

2022-11-13 20:28:40

李政

学长好厉害

2022-09-20 09:59:26

杨晨旭

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.6 （C++代码）

大神老白（C语言代码）

Tom数（C++代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

筛选N以内的素数

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

1908题解

sizeof的大作用（C语言代码）

Tom数（C语言代码）

C二级辅导-进制转换（C语言代码）

川哥的吩咐（C语言代码）

整数平均值（C语言代码）

C语言训练-自守数问题（C语言代码）

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

盐水的故事（C语言代码）

杨晨旭

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.6 （C++代码）

大神老白 （C语言代码）

Tom数 （C++代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

筛选N以内的素数

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

1908题解

sizeof的大作用 （C语言代码）

Tom数 （C语言代码）

C二级辅导-进制转换 （C语言代码）

川哥的吩咐 （C语言代码）

整数平均值 （C语言代码）

C语言训练-自守数问题 （C语言代码）

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

盐水的故事 （C语言代码）

大神老白（C语言代码）

Tom数（C++代码）

　　评论区

sizeof的大作用（C语言代码）

Tom数（C语言代码）

C二级辅导-进制转换（C语言代码）

川哥的吩咐（C语言代码）

整数平均值（C语言代码）

C语言训练-自守数问题（C语言代码）

盐水的故事（C语言代码）