Question

在c语言编程中“求100~200间的全部的素数”为什么会用到开平方呢

就是如下程序#include<stdio.h> #include<math.h> void main() { int m; int k; int i; int n=0; for(m=101;m<=200;m=m+2) { k=sqrt(m); for(i=2;i<=k;i++) if(m%i==0) break; if(i>=k+1) { printf("%d\n",m); n=n+1; } if(n%10==0) printf("\n"); } printf("\n"); } 为什么要这样？不明白，还有不是从100开始吗？为什么程序中是从101开始的呢？求解答！！！

Answer 1

这是一个数学问题。
质数的定义为，除了1和本身，没有其它因子，即没有其它数可以被其整除。
对于任意的数n，因子肯定是比n小的数，所以如果m>n，那么m不可能是n的因子。
于是最直观的判断方法就是，从1一直到n计算模除，获取到因子总数，如果总数为2，那么就是质数。
这样对于任意的n，判断质数就需要做n次模除。为了使程序优化，可以修改为，对2到n-1做模除，只要有一个可以整除，那么就不是整数。
对于这样的算法，可以再次优化。
如果n有一个引子m， 那么可以写作n = m*k的形式，那么m和k不可能同时大于n的平方根s。
这一点可以用反证法来证明。
如果m>s 且k>s
那么m*k > s*s
于是得到n>n的结论。明显是错误的。
于是m和k至少有一个是小于等于s的。
这样在判断质数时，只需要从2一直到s做模除，就可以准确的判断是否有其它因子，从而得到是否为质数的结论。
这就是为什么在判断质数中的程序中会用到求平方根的原因。其本质原因是为了减少模除次数，提高效率。

Answer 2

关于开平方的问题，首先肯定如果改成for(i=2;i<m;i++)这个程序也是对的。那为什么要用k呢？因为如果m是一个合数，那么他肯定是由两个数相乘的，而这两个数最接近的情况就是都是m的开平方。除此之外的情况下，这两个数必然有一个大于m的开平方，一个小于m的开平方。而检验是否为合数只要检验是否能被这两个数中任意一个数整除就行，所以只要检查较小的那个数，所以用i<=k，i就会取到所有较小的那个数可能的值。
关于101开始的问题请看最外层循环for(m=101;m<=200;m=m+2)。很明显，程序员直接把偶数的情况排除了，只考虑了奇数。（因为偶数肯定不是素数嘛- -！）
这两个细节都让整个程序的循环次数大大减少，提高了效率。

Answer 3

不用也可以， k=sqrt(m); for(i=2;i<=k;i++) 这个可以换成
for(i=2;i*i<=m;i++)

为什么需要这个sqrt(m)，其实是为了减少循环次数而已
有三个循环次数，一个是m-1，一个是m/2（m的一半），最后一个是sqrt(m)，这三个数，都可以，但是sqrt(m)最小
m-1不用说，肯定是可以的，素数的定义就是这样
m/2这个也是可以的，M/2~m之间肯定不会有他的因子，因为这个区间的数值乘以最小的系数2都比m大
sqrt(m)这个难理解一点。因为某个数的因子肯定是围绕sqrt(m)这个数值的在两边排列的
也就是说，在1~sqrt(m)之间有个因子，那么m除以这个因子得到的数值肯定在sqrt(m)~m之间，所以计算一次就够了
而且sqrt(m)这个数值比m/2要小，所以为了减少计算次数，用这个是最好的

100肯定不是素数，这是定下的，呵呵