杨晨旭

用户名：dotcpp0598807

访问量：4650

签　名：

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

　　自我简介：

TA的其他文章

明明的随机数
浏览：119

你可能喜欢

筛选N以内的素数

　　作者: 杨晨旭　　　　发表时间：2022-09-20 00:02:16 浏览：4429　|　评论：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

黄小橘

#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语言程序设计教程（第三版）课后习题1.6 （C语言代码）

【明明的随机数】（C语言代码）

DNA （C++代码）

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

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

筛选N以内的素数

评论区

精彩推荐

P1001 （C语言代码）

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

WU-输出正反三角形（C++代码）

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

K-进制数（C语言描述，蓝桥杯）

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

A+B for Input-Output Practice (III) （C语言代码）

小九九（C语言描述,不看要求真坑爹）

C二级辅导-计负均正（C语言代码）

Hello, world! （C语言代码）

杨晨旭

TA的其他文章

你可能喜欢

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

【明明的随机数】 （C语言代码）

DNA （C++代码）

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

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

筛选N以内的素数

评论区

精彩推荐

P1001 （C语言代码）

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

WU-输出正反三角形 （C++代码）

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

K-进制数 （C语言描述，蓝桥杯）

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

A+B for Input-Output Practice (III) （C语言代码）

小九九 （C语言描述,不看要求真坑爹）

C二级辅导-计负均正 （C语言代码）

Hello, world! （C语言代码）

【明明的随机数】（C语言代码）

　　评论区

WU-输出正反三角形（C++代码）

K-进制数（C语言描述，蓝桥杯）

小九九（C语言描述,不看要求真坑爹）

C二级辅导-计负均正（C语言代码）