Question

C++语言问题，关于编程一个显示从1到100的质数。

#include<iostream>
using namespace std;
int main(){
int i, j, k, n;
for (i = 2; i <= 100; i++)
{
k = 1;
n = sqrt(i);
for (j = 2; j <= n; j++)
if (i%j == 0)
{
k = 0;
break;
}
if (k == 1)
cout << i << "是质数" << endl;
}
return 0;
}

为什么要有n=sqrt(i);语句，而不是在for 语句中的j<=n;改为j<=i;
请高手解答！

Answer 1

假如某个数n不是素数，则一定可以分解成x*y形式。
由此可以推论，n不是素数，则一定可以被某个小于n的数整除。
而对n来说，最小公因数最大只可能为n的平方根，因为假如存在一个大于n平方根的公因数x，则一定存在另一个公因数y＝n/x, y<x。从上面的推理可以得出结论，如果n不能被所有小于等于它的平方根的整数整除，则n为素数
像你那样也对，可是n后面的循环都浪费掉了，这样提高了效率

追问

可是按照我那想法去编译运行程序，却不显示结果，为什么？

追答

for (j = 2; j <= n; j++)//这里=号要去掉啊，不然一定会被自身给break出去

追问

对哦，- -！有点白痴了！ 非常感谢你！

Answer 2

加一个sqrt执行次数很明显减少，不必要的循环次数去掉

根据数学知识，这样做是没问题的~