算法基础-数学知识

她的店里只卖樱花

发布于 2022-10-31 16:40:46

4100

发布于 2022-10-31 16:40:46

文章被收录于专栏：常用算法模板

质数

01.试除法判定质数

题目描述

给定 n 个正整数a_i，判定每个数是否是质数。

输入格式

第一行包含整数 n。

接下来 n 行，每行包含一个正整数 a_i。

输出格式

共 n 行，其中第 i 行输出第 i个正整数 a_i 是否为质数，是则输出 Yes，否则输出 No。

数据范围

1\le n\le 100,1\le a_i\le 2 ^ {31} - 1

输入样例：

2
2
6

输出样例：

Yes
No

题解

时间复杂度

O(\sqrt{n})

核心思想

枚举一遍就好了

核心函数

bool is_pr(int x){
    if(x < 2) 
        return false; 
    for(long long i = 2; i * i <= x; i ++)
        if(x % i == 0)
            return false; 
    return true; 
}

代码实现

#include <iostream>

using namespace std; 

bool is_pr(int x){
    if(x < 2) 
        return false; 
    for(long long i = 2; i * i <= x; i ++)
        if(x % i == 0)
            return false; 
    return true; 
}

int main (){
    int n; 
    cin >> n; 
    while(n --)
    {
        int x; 
        cin >> x; 
        cout << (is_pr(x) ? "Yes" : "No") << endl;  
    }
    
    return 0; 
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-04-21，如有侵权请联系 cloudcommunity@tencent.com 删除

基础