小朋友学算法（4）：求质数的三种基础方法

た入场券 2022-03-29 05:20 270阅读 0赞

# 方法一 #

#include<iostream>
    using namespace std;
    
    int main()
    { 
        int n;
        cin >> n;
    
        int cnt = 0;
        for(int i = 1; i <= n; i++)
        { 
            if(0 == n % i)
            { 
                cnt++;
            }
        }
    
        cout << (2 == cnt ? "YES" : "NO");
    
        return 0;
    }

运行结果：

17
    YES

时间复杂度：运行时间较长，需要判断n次。效率较低。

# 方法二 #

#include<iostream>
    using namespace std;
    
    bool isPrime(int x)
    { 
        if(x <= 1)
        { 
            return false;
        }
    
        for(int i = 2; i < x; i++)
        { 
            if(0 == x % i)
            { 
                return false;
            }
        }
    
        return true;
    }
    
    int main()
    { 
        int n;
        cin >> n;
        cout << (isPrime(n) ? "YES" : "NO");
    
        return 0;
    }

运行结果：

17
    YES

时间复杂度：运行时间较长，需要判断n-1次。效率较低。

# 方法三 #

#include<iostream>
    #include<cmath>
    using namespace std;
    
    bool isPrime(int x)
    { 
        if(x <= 1)
        { 
            return false;
        }
    
        int root = sqrt(x);
        for(int i = 2; i <= root; i++)
        { 
            if(0 == x % i)
            { 
                return false;
            }
        }
    
        return true;
    }
    
    int main()
    { 
        int n;
        cin >> n;
        cout << (isPrime(n) ? "YES" : "NO");
    
        return 0;
    }

运行结果：

17
    YES

时间复杂度：O(sqrt(n))。效率较高。

发表评论取消回复

表情：

评论列表（有 0 条评论，270人围观）

还没有评论，来说两句吧...

相关阅读

相关使用java，求质数的4种方法

![822f86da087553328500c99a2b4b9d18.jpeg][] 的方法：用一个数x去除2至sqrt(x)（即该数的开方），如果能被整除，则

布满荆棘的人生/ 2024年04月01日 18:27/ 0 赞/ 70 阅读

相关 java求质数的4种方法分享

判断素数的方法：用一个数x去除2至sqrt(x)（即该数的开方），如果能被整除，则表明此数不是素数，反之是素数。第一种：双重for循环使除数与被除数个个计算，效率极低

比眉伴天荒/ 2024年03月27日 13:25/ 0 赞/ 69 阅读

相关使用java判断质数的三种方法

> 方法一：质数只能被1和它本身整除 import java.util.Scanner; public class Test { p

￡神魔★判官ぃ/ 2024年03月27日 09:01/ 0 赞/ 65 阅读

相关求质数算法的N种境界 (N > 10)

★引子　　前天，俺在《 [俺的招聘经验\[4\]：通过笔试答题能看出啥？][4] 》一文，以"求质数"作为例子，介绍了一些考察应聘者的经验。由于本文没有政治敏感内容，顺

朱雀/ 2022年08月26日 08:44/ 0 赞/ 193 阅读

相关求质数的几种算法

转载自：http://blog.sina.com.cn/s/blog\_622e77cc0100n5lm.html 1、根据质数的定义求　　质数定义：只能被1或者自身整除

梦里梦外;/ 2022年08月21日 13:42/ 0 赞/ 321 阅读

相关小朋友学算法（2）：求排列数

关于排列的介绍，可以参考[小朋友学奥数（11）：排列][11] 程序： include <iostream> using namespace std;

待我称王封你为后i/ 2022年05月23日 08:28/ 0 赞/ 143 阅读

相关小朋友学算法（3）：求组合数

关于组合的介绍，可以参考[小朋友学奥数（12）：组合][12] \一、利用基本公式，递归 include <iostream> using namespac

绝地灬酷狼/ 2022年05月23日 08:28/ 0 赞/ 222 阅读

相关小朋友学算法（1）：求幂pow函数的四种实现方式

`更新时间：2020-5-4` 在math.h中，声明了一个函数pow(x, n)，用于求x的n次方。假如咱们不调用math.h中的pow函数，如何实现求x ^ n的算法呢？

ゝ一世哀愁。/ 2022年05月23日 07:05/ 0 赞/ 235 阅读

相关小朋友学算法（4）：求质数的三种基础方法

方法一 include<iostream> using namespace std; int main() {

た入场券/ 2022年03月29日 05:20/ 0 赞/ 271 阅读

相关小朋友学经典算法（17）：分治法求众数

一组数据中，出现次数最多的数就叫这组数据的众数。如果有两个或两个以上个数出现次数都是最多的，那么这几个数都是这组数据的众数。如果所有数据出现的次数都一样，那么这组数

今天药忘吃喽~/ 2022年03月01日 21:00/ 0 赞/ 210 阅读