求两个数C 质数 时间限制:1.00s内存限制:16.00MB 题目背景 质数是指除了1和本身之外没有其他约数的数,如7和11都是质数,而6不是质数,因为6除了约数1和6之外还有约数2和3。输入一个正整数,判断它是否为质数,如是质数则输出“Yes”,否则输出这个数的大于1的最小的约数。 输入格式 仅有一行包含一个正整数n,其中 输出格式 仅有一行,如果从输入文件读入的数是质数则输出“Yes”,否则输出这个数的大于1的最小的约数。 输入输出样例字的最小公倍数
时间: 2024-02-13 16:04:28 浏览: 46
以下是 C++ 实现代码,使用试除法判断质数,如果不是质数则在 $[2,\sqrt{n}]$ 的范围内寻找约数。
```cpp
#include <iostream>
#include <cmath>
using namespace std;
bool is_prime(int n) {
if (n <= 1) return false;
int sqrtn = sqrt(n);
for (int i = 2; i <= sqrtn; i++) {
if (n % i == 0) return false;
}
return true;
}
int main() {
int n;
cin >> n;
if (is_prime(n)) {
cout << "Yes" << endl;
} else {
int sqrtn = sqrt(n);
for (int i = 2; i <= sqrtn; i++) {
if (n % i == 0) {
cout << i << endl;
return 0;
}
}
cout << n << endl;
}
return 0;
}
```
时间复杂度为 $O(\sqrt{n})$。