#include<stdio.h>
#include<math.h>
int isprime(int n) {
if (n==1) {
return 0;
}
if (n==2) {
return 1;//2是素数
}
if (n%2==0) {
return 0;//偶数不是素数
}
//检查从3到sqrt(n)的所有奇数是否能整除n
int i;
for (i=3;i<=sqrt(n);i+=2) {
if (n%i==0) {
return 0;
}
}
return 1;
}
int main()
{
int t;
scanf("%d",&t);
while (t>0) {
int n;
scanf("%d",&n);
if (isprime(n)) {
printf("Yes\n");
} else {
printf("No\n");
}
t--;
}
return 0;
}
我的比较复杂,想了好久。
今天学习的知识点是:
在判断一个数 n 是否为素数时,循环条件 i <= sqrt(n)(i 为可能的除数)是一种基于数学原理的优化,目的是减少不必要的计算,提高判断效率。
任何一个合数 n(非素数)都可以表示为两个整数的乘积:n = a × b,其中 a 和 b 都是 n 的因数(a ≤ b)。
此时必然满足:a ≤ sqrt(n) 且 b ≥ sqrt(n)。
-
例如:n = 12,其因数对为 (2,6)、(3,4)。
sqrt(12) ≈ 3.46,其中 2 ≤ 3.46 且 6 ≥ 3.46,3 ≤ 3.46 且 4 ≥ 3.46。
证明:
假设 n 是合数,但所有因数都大于 sqrt(n),则会出现矛盾:
设 a 和 b 是 n 的两个因数,且 a > sqrt(n),b > sqrt(n),
则 a × b > sqrt(n) × sqrt(n) = n,与 a × b = n 矛盾。
因此,合数必然存在小于等于 sqrt(n) 的因数。
设 a 和 b 是 n 的两个因数,且 a > sqrt(n),b > sqrt(n),
则 a × b > sqrt(n) × sqrt(n) = n,与 a × b = n 矛盾。
因此,合数必然存在小于等于 sqrt(n) 的因数。

京公网安备 11010502036488号