Question

判断数n是否为素数时，只需看能否被2到根号n之间的数整除，这是为什么？没有别的算法吗？

判断m是否为素数？ 程序如下： #include <stdio.h> #include <math.h> void 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 number\n",m); else printf("%d is not a prime numbei\n",m); } 我们都知道：所谓素数，就是除了1和它本身，不能被其他数整除的数。也称作质数。 下面是我自己根据上面的说法自行编的程序，不知道可不可以，还望广大老师指教。谢谢。请看下列程序： #include <stdio.h> void main() { int m,i; scanf("%d",&m); for(i>1,i<m,i++); if(m%i==o) continue; /* 如果用i被m能整除的话，则结束本次循环 */ printf("%d is not a prime number\n",m); else printf("%d is a prime number\n",m); }

Answer 1

因为如果一个数不是素数是合数， 那么一定可以由两个自然数相乘得到， 其中一个大于或等于它的平方根，一个小于或等于它的平方根。并且成对出现。 程序改了下： #include <stdio.h> int main(void) { int m,i; scanf("%d",&m); for(i=2;i<m;i++) { if(m%i==0) break; } if (i < m) printf("%d is not a prime number\n",m); else printf("%d is a prime number\n",m); return 0; }

Answer 2

有几个问题 i没有初始值 for(i>1,i<m,i++); 括号里面用;而不是, 最后一个;去掉 补充： 判断素数 的最优算法就是只判断2到根号n之间的数 如果你要判断2到m-1也是可以的 只是效率上不是最优