• L1-028 判断素数


    一、题目再现

    本题的目标很简单,就是判断一个给定的正整数是否素数。

    输入格式:

    输入在第一行给出一个正整数N(≤ 10),随后N行,每行给出一个小于2^31的需要判断的正整数。

    输出格式:

    对每个需要判断的正整数,如果它是素数,则在一行中输出Yes,否则输出No

    输入样例:

    1. 2
    2. 11
    3. 111

    输出样例:

    1. Yes
    2. No

    二、思路 

    本题的难点在于素数的定义以及判断素数的函数的编写;还有一个运行超时问题。

    三、知识点

    素数的定义

    质数(Prime number),又称素数,指在大于1自然数中,除了1和该数自身外,无法被其他自然数整除的数(也可定义为只有1与该数本身两个正因数的数)。大于1的自然数若不是质数,则称之为合数(也称为合成数)。

    sqrt函数

    C ++中的sqrt()函数返回数字的平方根

     √x = sqrt(x)

    此函数在头文件中定义。

    四、问题

    超时问题://用i*i<=n 就会超时;用i <= sqrt(n)就可以

    在一般情况下,乘法运算通常比sqrt(开方运算)要快。乘法运算是计算机硬件中的基本运算之一,通常在硬件级别进行高度优化,因此速度较快。sqrt运算涉及更复杂的数学操作,可能需要更多的计算资源,因此相对较慢。

    但是,在本题中需要判断的数据为小于2^31,也就是说可能数据会很大,那么sqrt函数的运行时间可能要比乘法的少【个人理解】

    五、AC代码

    1. #include
    2. #include
    3. using namespace std;
    4. bool isPrime(int n) {
    5. /*质数(Prime number),又称素数,指在大于1的自然数中,除了1和该数自身外,无法被其他自然数整除的数
    6. (也可定义为只有1与该数本身两个正因数的数)。大于1的自然数若不是质数,则称之为合数(也称为合成数)。*/
    7. //一个数如果能被 除了1和该数自身外 的自然数 整除,那么return false ;否则return true
    8. if (n <= 1) {
    9. return false; // 1和负数都不是素数
    10. }
    11. if (n <= 3) {
    12. return true; // 2和3是素数
    13. }
    14. // 检查是否可以被2或3整除
    15. if (n % 2 == 0 || n % 3 == 0) {
    16. return false;
    17. }
    18. // 检查是否可以被6k ± 1的形式整除,其中k是正整数
    19. //例如 6k ± 1在1~10中为5,7 其他的数字上面已经判断了。
    20. //比如1是第一if语句
    21. //2的倍数 2、4、6能被2整除(第三个if语句)
    22. //3的倍数 3、6、9能被3整除(第三个if语句)
    23. for (int i = 5; i <= sqrt(n); i += 6) {//用i*i<=n 就会超时
    24. if (n % i == 0 || n % (i + 2) == 0) {
    25. return false;
    26. }
    27. }
    28. return true;
    29. }
    30. int main() {
    31. int n;
    32. cin >> n;
    33. int m[10];
    34. for (int i = 0; i < n;i++)
    35. {
    36. cin >> m[i];
    37. if (isPrime(m[i]))
    38. {
    39. cout << "Yes" << endl;
    40. }
    41. else
    42. {
    43. cout << "No" << endl;
    44. }
    45. }
    46. return 0;
    47. }

    其他判断一个数是否为素数的函数(我还没太理解)

    1. bool isPrime(int n) //判断素数
    2. {
    3. if(n <= 1)
    4. {
    5. return false;
    6. }
    7. for(int i = 2; i <= sqrt(n); i++)
    8. {
    9. if(n%i == 0)
    10. {
    11. return false;
    12. }
    13. }
    14. return true;
    15. }

    欢迎评论区交流~

  • 相关阅读:
    数据结构从入门到精通——算法的时间复杂度和空间复杂度
    智能矩阵,引领商业新纪元!拓世方案:打破线上线下界限,开启无限营销可能!
    docker之安装mongo创建运行环境
    网上那么多教人赚钱的方法,但是你实际上是靠什么赚钱的呢?
    软件工程:墨菲定律,潜在问题管理的艺术
    【RcoketMQ】RcoketMQ 5.0新特性(二)- Pop消费模式
    Spark性能调优之广播变量
    Netty 进阶学习(十)-- 协议设计与解析
    炒股使用杠杆的原理是为什么?
    JS基础知识
  • 原文地址:https://blog.csdn.net/zss6666yi/article/details/133067275