每日一题——判断素数-阿里云开发者社区

每日一题——判断素数

2023-04-20 160

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 每日一题——判断素数

哈喽大家好，我是保护小周ღ，本期为大家带来的是编程实现输入一个数判断他是否为素数，博主将使用2种方法解答此题，一起来看看有没有大家平时使用的方法啊~

编辑

题目：

从键盘输入一个整数，判断该数是否素数。素数是只能被1 和本身整除的数。

博主在这里分享两种方法

第一种是比较常用的穷举法。

第二种使用sqrt()函数;取平方根，判断至平方根即可。

废话少说直接上代码：

穷举法

使用穷举法来判断一个数是否是素数，即将该整数依次除以2、3、……n-1，

如果全部不能被整除，即为素数，如果被其中任何一个整除，则不为素数。

#define _CRT_SECURE_NO_WARNINGS#include<stdio.h>intmain()
{
intm=0;
printf("请输入一个整数,判断它是否为质数：\n");
while (scanf("%d", &m) !=EOF)
    {
inti=0;
//遍历所以的可能性for (i=2; i<m; ++i)
        {
if (m%i==0)//如果该数m整除了，则说明该数不是素数            {
break;//中止循环            }
        }
//最后如果循环不是被break;中止的，执行++i，后i==m;if (i==m)
        {
printf("This is a prime number！\n");
        }
else        {
printf("This is not a prime number！\n");
        }
    }
return0;
}

编辑

判断至平方根：

所谓素数就是只能被1和其本身所整除的数。当进行质数判断的时候不需要判断到全部的数字，只需要判断到平方根就可以了。

判断一个数m是否为素数的算法：

令n=m开二次方向下取整

循环检查从2开始到n的每一个数字是否能整除m,如果能，终止循环，返回m非素数

循环结束，m是为素数

关于开二次方啊，就设计到一个知识点，咱们要使用 math.h 库里面的一个数学函数sqrt();专门开平方用的。#include<mathh> 开头声明一下。

#define _CRT_SECURE_NO_WARNINGS#include<stdio.h>#include<math.h>//数学函数都在这个头文件里intmain()
{
intm=0;
printf("请输入一个整型数字判断是否为素数：\n");
while (scanf("%d", &m)!=EOF)
    {
intk=sqrt(m);//将m开方的值给k存储inti=0;
for (i=2; i<=k; i++)//判断至平方根        {
if (m%i==0)
break;
        }
if ((i>k) &&m!=1&&m!=0)//0,1是两个特殊用例，暴力破解printf("%d is a prime number\n", m);
elseprintf("%d is not a prime number:\n", m);
    }
return0;
}