算法刷题笔记 试除法判定质数（C++实现）

题目描述

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

输入格式

• 第一行包含整数n。
• 接下来n行，每行包含一个正整数ai。

输出格式

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

数据范围

• 1 ≤ n ≤ 100
• 1 ≤ ai ≤ 2^31−1

基本思路

• 本题只需要按照顺序，从2开始，遍历所有比ai小的数字，判定是否可以整除即可。
• 遍历的上限可以优化，从ai-1降低到ai的平方根，这是因为ai如果不是素数，存在因子的话，其因子也是成对出现的，其中一个因子大于等于ai的平方根，另一个因子小于等于ai的平方根。
• 出于效率考虑，可以计算一次ai的平方根，而不是每次迭代的过程中都进行计算，这样可以提升算法的执行效率。

实现代码

#include <cstdio>
#include <cmath>// 【变量定义】数据的个数
int n;
// 【变量定义】每一轮需要判定是否为质数的数字
int x;// 【函数定义】判定一个数字是否是质数的函数
void is_prime(int x)
{// 特殊情况：如果x等于1，则直接判定不是质数，返回结果if(x == 1) {printf("No\n");return;}// 提前计算好该数字的平方根，防止多次计算浪费资源int temp = sqrt(x);// 记录该数字是否是质数bool prime = true;// 通过遍历的方式查找该数字是否有约数for(int i = 2; i <= temp; ++ i){if(x % i == 0){prime = false;break;}}// 根据计算结果进行输出if(prime == true) printf("Yes\n");else printf("No\n");
}int main(void)
{// 【变量输入】输入需要判定的数字的个数scanf("%d", &n);// 【变量输入】输入需要判定的每一个数字for(int i = 0; i < n; ++ i){scanf("%d", &x);// 【数字判定和结果输出】通过自定义的is_prime函数判定一个数字是否是质数is_prime(x);}
}