查人人中国名人网南京玄武区女副区长:笨小孩提问....
来源：百度文库 编辑：查人人中国名人网 时间：2024/04/27 23:11:08
今天在家看潭浩强的C程序设计~
看到第三个例子判断m是否是素数
他采用的算法是让m被2到根号下M整除~~如果m能被2到根号下m中任意一个整数整除则~循环提前结束~
请问数学原理是什么呀??讲细一点我很笨....
#include<math.h>
main()
{
int m,i,k;
scanf("%d",&m);
k=sqrt(m);
for(i=2;i<=k;i++)
if(m%i==0)break;
if(i>k)printf("%d is a prime muber\n",m);
else printf("%d is not a prime number\n",m);
}
若一个自然数m不是质数，则必然能表示成两个自然数m1和m2之积，并且其中之一必然小于等于sqrt(m)，另一个必然大于等于sqrt(m)。
所以要判断一个自然数m是否为素数，可简化为判断它能否被2至sqrt(m)之间的自然数整除即可
这个是定理(高等数学的内容吗?)
郁闷呀...我只上过高中....
看到第三个例子判断m是否是素数
他采用的算法是让m被2到根号下M整除~~如果m能被2到根号下m中任意一个整数整除则~循环提前结束~
请问数学原理是什么呀??讲细一点我很笨....
#include<math.h>
main()
{
int m,i,k;
scanf("%d",&m);
k=sqrt(m);
for(i=2;i<=k;i++)
if(m%i==0)break;
if(i>k)printf("%d is a prime muber\n",m);
else printf("%d is not a prime number\n",m);
}
若一个自然数m不是质数，则必然能表示成两个自然数m1和m2之积，并且其中之一必然小于等于sqrt(m)，另一个必然大于等于sqrt(m)。
所以要判断一个自然数m是否为素数，可简化为判断它能否被2至sqrt(m)之间的自然数整除即可
这个是定理(高等数学的内容吗?)
郁闷呀...我只上过高中....
可以这样理解:
首先,你应该明白什么是素数,素数是指只能被1和它本身整除的数.还要明白,1既不是素数也不是合数(合数是指除1和素数的整数)
然后,明白上面这一点后,我们来看个例子,比如说9就不是素数,因为他除了能被1和它本身(9)整除之外还能被3整除.
好,下面我们来证明那个定理:
假设A是一个不是素数,那么也就是说它除能被1和A整除外,它还能够被另一个数B整除,也就是说A/B=另一个整数C,换过来,于是A/C=B,所以A除了能被1,A,B整除之外,还能被C整除,好,现在我们来研究数B,C和D=sqrt(A)之间的关系,看是不是一个数大于D那么另一个就小于D.假设B>D同时C>D,那么B*C>D*D=A这与A/B=C即B*C=A相矛盾,同样可证明B<D,C<D也不成立,于是只可能B<D,C>D或者B>D,C<D.
若一个自然数m不是质数，则必然能表示成两个自然数m1和m2之积，并且其中之一必然小于等于sqrt(m)，另一个必然大于等于sqrt(m)。
所以要判断一个自然数m是否为素数，可简化为判断它能否被2至sqrt(m)之间的自然数整除即可
这个高中数学里好像没讲，但我们可以证明。假设一个自然数可以分解为两个比它的平方根大的自然数相乘，那么我们通过计算可以知道这个等式是不成立的。一位贴公式比较困难，这里不能详尽。