每日一题——判断素数

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

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

image.gif编辑

题目:

从键盘输入一个整数,判断该数是否素数。素数是只能被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;
}

image.gif

image.gif编辑


判断至平方根:

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

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

    1. 令n=m开二次方向下取整
    2. 循环检查从2开始到n的每一个数字是否能整除m,如果能,终止循环,返回m非素数
    3. 循环结束,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;
    }

    image.gif

    image.gif编辑


    感兴趣的朋友可以用博主的方法,或者是自己的方法做做这道题,优化一下代码,尝试怎样判断某一个区间内的素数,并将他们都输出来。

    分享一个牛客网上类似的题目,大家也可以尝试着做一做。

    链接:区间素数__牛客网

    本期收录于博主的专栏——每日一题,适用于编程初学者,有兴趣的朋友们可以订阅,查看其它“精彩小题”。每日一题_保护小周ღ的博客-CSDN博客

    感谢每一个观看本篇文章的朋友,更多精彩敬请期待:保护小周ღ  *★,°*:.☆( ̄▽ ̄)/$:*.°★*

    image.gif编辑

     如有侵权请联系修改删除!

    相关文章
    |
    JavaScript 前端开发 C语言
    leetcode每日一题 2021/4/1 1006. 笨阶乘
    leetcode每日一题 2021/4/1 1006. 笨阶乘
    39 0
    Leecode 18. 四数之和
    Leecode 18. 四数之和
    51 0
    |
    算法 C++ Python
    每日算法系列【LeetCode 1006】笨阶乘
    每日算法系列【LeetCode 1006】笨阶乘
    |
    算法
    【AcWing&&牛客】打表找规律
    【AcWing&&牛客】打表找规律
    89 0
    LeetCode每日一题(23)——最大三角形面积
    最大三角形面积 1.题目 2.示例 3.思路 4.代码 暴力穷举 凸包
    105 0
    LeetCode每日一题(23)——最大三角形面积
    LeetCode每日一题——812. 最大三角形面积
    给定包含多个点的集合,从其中取三个点组成三角形,返回能组成的最大三角形的面积。
    84 0
    LeetCode每日一题——812. 最大三角形面积
    青蛙跳台阶
    青蛙跳台阶
    80 0
    |
    人工智能 算法 C++
    每日算法刷题Day11-最大公约数、数组去重
    ⭐每日算法题解系列文章旨在精选重点与易错的算法题,总结常见的算法思路与可能出现的错误,与笔者另一系列文章有所区别,并不是以知识点的形式提升算法能力,而是以实战习题的形式理解算法,使用算法。
    116 0
    每日算法刷题Day11-最大公约数、数组去重
    |
    算法
    『牛客|每日一题』逆波兰表达式
    基础算法无论在研究生面试还是求职面试都是十分重要的一环,这里推荐一款算法面试神器:牛客网-面试神器;算法题只有多刷勤刷才能保持思路与手感,大家赶紧行动起来吧(温馨提示:常见的面试问答题库也很nice哦 https://www.nowcoder.com/link/pc_csdncpt_ll_sf
    88 0
    『牛客|每日一题』逆波兰表达式