合数与质数的性质
发布时间
阅读量：
阅读量
质数定义
如果一个数为质数，则他只有他本身和1两个公因子(约数)，否则为合数。
编写一个程序判断某个数是否为质数
假设有待判断的数据为...：
通常的方法是从...开始依次检查是否能被...整除，在区间[..., ...−1]中是否存在能整除...的数值。
若有这样的情况发生，则判定数据...不是质数；
否则则确定数据...为质数。
程序实现如下：
#include<math.h>
#include<iostream>
using namespace std;
int main()
{
int N,i=2;
cin>>N;
for(i=2;i<N;i++)
{
if(N%i==0)
{
cout<<"false";
break;
}
if(i==N)
cout<<"true";
}
return 0;
}这一思路确实可行；但当数据量极大时，则会占用大量时间显然无法在规定时间内完成任务；因此有必要应用合数特性来优化算法效率。
合数性质
我们都知道，除1之外，任何正整数要么是质要么是合数，如果确定一个数是质数，那他就不可能是合数，同样，如果确定一个数不是合数，那么他一定是质数。所以可以通过判断一个数是不是合数，进而确定那个数是否是质数。
合数性质：如果一个数为合数，则该合数必然有一个公因子在（1~该数开平方根]之间，如果在这个区间内都找不到一个公因子，则该数必然是质数。这就是合数的重要性质。利用这个性质，我们可以通过修改上述程序来判断是否为质数。
证明如下：
合数有如下两个事实：
- 合数N=m*n；
- 合数N=（根号N） _（根号N）
结论：
如果 根号N 大于m，则n必然小于 根号N，同理
如果 根号N 小于m，则n必然大于 根号N，
如果 根号N 等于m，则n必然等于 根号N；
也就是说，m和n必然有一个是小于或者等于 根号N的。
解释：
不会出现m和n均大于 根号N的情况，因为如果这种情况出现的话，m_n必然大于 根号N 根号N，也就是m n>N。这和事实矛盾
也不会出现m和n均小于 根号N的情况，因为如果这种情况出现的话，则m*n必然小于N。
判断一个数是否为质数的程序更改如下：
#include<math.h>
#include<iostream>
using namespace std;
int main()
{
int N,i=2,flag=0;
cin>>N;
for(i=2;i<=sqrt(N);i++)
{
if(N%i==0)
{
cout<<"false";
flag=1;
break;
}
}
if(flag==0)
cout<<"true";
return 0;
}该代码相较于上述代码，在判断一个本来就是质数的数字N是否为质数时，则减少了计算√N减一倍的数量级。我们可以通过以下测试来对比两者的计算量及其执行效率。
#include<iostream>
#include<time.h>
using namespace std;
int main()
{
int N,i,compare = 0;
clock_t start,end;
cout<<"please input your number:";
cin>>N;
start=clock();
for(i=2;i<N;i++)
{
compare++;
if(N%i==0)
{
cout<<"false"<<endl;
break;
}
}
if(i==N)
cout<<"true"<<endl;
end=clock();
double seconds =(double)(end - start)/CLOCKS_PER_SEC;
cout<<"总共比较次数:"<<compare<<"次"<<endl;
cout << "运行时间：" << seconds << "s" << endl;
return 0;
}改进算法：（使用合数性质）
#include<iostream>
#include<math.h>
#include<time.h>
using namespace std;
int main()
{
int N,i,compare = 0,flag=0;
clock_t start,end;
cout<<"please input your number:";
cin>>N;
start=clock();
for(i=2;i<=sqrt(N);i++)
{
compare++;
if(N%i==0)
{
cout<<"false"<<endl;
flag=1;
break;
}
}
if(flag==0)
cout<<"true"<<endl;
end=clock();
double seconds =(double)(end - start)/CLOCKS_PER_SEC;
cout<<"总共比较次数:"<<compare<<"次"<<endl;
cout << "运行时间：" << seconds << "s" << endl;
return 0;
}我们对上述两种程序分别输入相同的质数值，并对该种程序的运行时间进行了详细分析；原先算法的运行情况如下：
改进算法运行结果：
基于运行结果对比分析可知, 后者相比前者提升了大约10倍的效率, 这正是算法的魅力所在. 此外, 从上述详细推导可以看到, 深入学习算法能使其应用更加广泛和高效, 从而掌握各类算法技巧能在任何领域都将无所不能.
全部评论 (0)
还没有任何评论哟~