题目描述
一个大于 1 的自然数,如果除了 1 和它自身外,不能被其他自然数整除则称该数为质数。
例如 7 就是一个质数,因为它只能被 1 和 7 整除。
现在,给定你 N 个大于 1 的自然数,请你依次判断这些数是否是质数。
输入格式
第一行包含整数 N,表示共有 N 个测试数据。
接下来 N 行,每行包含一个自然数 X。
输出格式
每个测试用例输出一个结果,每个结果占一行。
如果测试数据是质数,则输出 X is prime,其中 X 是测试数据。
如果测试数据不是质数,则输出 X is not prime,其中 X 是测试数据。
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
时间复杂度较大
参考文献
C 代码
#include<stdio.h>
int main()
{
int n,b,i,c;
int a[101];
scanf("%d\n",&n);
for(i=1;i<=n;i++){
scanf("%d\n",&a[i]);
}
for(i=1;i<=n;i++)
{ int d=0;
for(b=2;b<a[i];b++)
{
if(a[i]%b==0)
{
d=1;
break;
}
}
if(d==1)
{
printf("%d is not prime\n",a[i]);
}
else
printf("%d is prime\n",a[i]);
d=0;
}
return 0;
}
此代码运行3456ms左右;
一满足条件退出即可
blablabla
算法2
使b<=a[i]/b;
通过缩小循环范围来减小时间复杂度,也许有人会问,为什么要给a[i]/b呢;
首先我们判断的是是否为质数;如果一个如果一个数可以整除4,必然可以整除2;那么它必然不是不是质数,直接跳出循环即可;否则是质数;
blablabla
时间复杂度
参考文献
C++ 代码
#include<stdio.h>
int main()
{
int n,b,i,c,d;
int a[101];
scanf("%d\n",&n);
for(i=1;i<=n;i++){
scanf("%d\n",&a[i]);
}
for(i=1;i<=n;i++)
{ d=1;
for(b=2;b<=a[i]/b;b++)
{
if(a[i]%b==0)
{
d=0;
break;
}
}
if(d==0)
printf("%d is not prime\n",a[i]);
else
printf("%d is prime\n",a[i]);
}
return 0;
}
//优化之后用了12ms;
come on,come true;