Is_prime专题

说道质数判定,就不得不说到函数

如果连函数都不知道的,请看 函数
现在进入正题
怎么判断是否为质数呢?很简单,只要又一个循环变量一个一个试验,看他是否能整除就行了
代码如下

1
2
3
4
5
6
7
8
9
10
11
bool Is_prime(int x)//声明一个布尔形函数,函数名为Is_prime
{
for(int i=1;i<=x;i++)//用1到x的数取余,不能整除返回false
{
if(x%i!=0)
{
return false;
}
}
return true;//如果不能返回true
}

可是如上跑的太慢,怎么优化呢?
可以直接从2到x的平方根进行判断
代码如下

1
2
3
4
5
6
7
8
9
10
11
bool Is_prime(int x)//声明一个布尔形函数,函数名为Is_prime  
{
for(int i=2;i<=sqrt(x+0.5);i++)//用2到x的平方根取余,不能整除返回false
{
if(x%i!=0)
{
return false;
}
}
return true;//如果不能返回true
}

上代码的sqrt(x+0.5)反复计算,浪费时间,还可以一次算好

1
2
3
4
5
6
7
8
9
10
11
12
bool Is_prime(int x)//声明一个布尔形函数,函数名为Is_prime  
{
int q=sqrt(x+0.5);
for(int i=2;i<=q;i++)//用2到x的平方根取余,不能整除返回false
{
if(x%i!=0)
{
return false;
}
}
return true;//如果不能返回true
}