c++在求素数中为什么要先开平方？如何遍历判断素数？素数是只有1和本身能整除的整数。所以在求素数的时候，要将素数与1到素数本身中间的所有整数都相除，看是否有整除的数，如果有，那肯定不是素数了。但是从算法上考虑，为了减少重复量，开平方后面的数就不用相除了，因为a/b（平方数）=c（小一点的数），同样a/c=b。举例说明：
25，开平方以后是5,那么整除2~5就可以了，如果有满足条件的，就是素数。

比如，24的因数有1、2、3、4、6、8、12、24
按定义应该用2－23去除，但经过分析上面的数可以发现
1×24、2×12、3×8、4×6
如果2、3、4是某个数的因数，那么另外几个数也是，反之也一样
所以为提高效率，可以只检查小于该数平方根的那些数，如24的平方根大于4小于5，检查2－4就可
不知说清楚了没有，呵呵
论坛建议、意见、吐槽专用贴对我有用[2] 丢个板砖[0] 引用 | 举报 | 管理
banhcenzhaij
banhcenzhaij
banhcenzhaij
等级：Blank
#2 得分：8 回复于： 2009-03-21 22:18:38
定义a=x*y (a,x,y都是正整数)
如果x和y都大于a的开平方
那么x*y>a,矛盾了.
所以必有一个数是小于等于a的开平方,如果这个数不等于1,那么a就是素数了.
2014年4月微软MVP当选名单揭晓！对我有用[0] 丢个板砖[1] 引用 | 举报 | 管理
cheng_fengming
cheng_fengming
cheng_fengming
等级：Blank
#3 得分：0 回复于： 2009-03-21 22:40:28
同意一楼说的 其实求素数完全可以根据素数的定义来判断
但是为了提高效率 对其开平方就可以了！
CSDN投诉事项说明对我有用[0] 丢个板砖[0] 引用 | 举报 | 管理
orangemike
orangemike
orangemike
等级：Blank
#4 得分：2 回复于： 2009-03-21 23:15:20
利用数学概念降低搜索范围.

如果真的存在a*b = n,其中b大于n^(1/2)那么必然有a小于n^(1/2).
对我有用[0] 丢个板砖[0] 引用 | 举报 | 管理
yang677888
yang677888
yang677888
等级：Blank
#5 得分：0 回复于： 2009-03-22 09:52:32
开方是为了减少除数的量，这样大大提高除数求余效率。开平方后面的数就不用相除了，因为开方得的数是除数最大因子了。 如81开方得9，9是除数最大因子，除数9后面的数就不用除了。

这是一个简单判断素数列子：（C语言主要代码）
bool IsPrime( int p )
{
for( int i = 2; i < p; i++ )
{
if( p%i == 0 )
return false;
}

return true;
}

要开方判断素数（C语言主要代码）
bool IsPrime( int p )
{
int bf = int( floor( sqrt( double(p) ) ) );

for( int i = 2; i <= bf; i++ )
{
if( p%i == 0 )
return false;
}

return true;
}
对我有用[0] 丢个板砖[0] 引用 | 举报 | 管理
yang677888
yang677888
yang677888
等级：Blank
#6 得分：0 回复于： 2009-03-22 10:00:07
这是输入一个数，判断有多少个素数
#include <iostream>

using namespace std;

bool IsPrime( int n )
{
int bf = int( floor( sqrt(n) ) );

for( int i = 2; i <= bf; i++ )
{
if( n%i == 0 )
{
return false;
}
}

return true;
}

int main()
{
int n, amount;

amount = 0;

cout << “Please input a number:”;

cin >> n;

unsigned int uiStart, uiStop;

uiStart = GetTickCount();

for( int i = 2; i < n; i++ )
{
if( IsPrime(i) )
{
amount++;
//cout << i << ” “;
}
}

cout << endl << “There is/are ” << amount
<< ” Prime Numbers between 1 and ” << n << endl;

return 0;
}
对我有用[0] 丢个板砖[0] 引用 | 举报 | 管理
tosshl
tosshl
tosshl
等级：Blank
#7 得分：2 回复于： 2009-03-22 11:06:14
a=(a^1/2)*(a^1/2)
如果a不是素数
那么a有一个因子b a=b*c;
那么a的因子中（b或c）必定有一个是小于等于a^1/2的
所以判断的时候不用判断到1-a，只需要1-a^1/2
对我有用[0] 丢个板砖[0] 引用 | 举报 | 管理
jiest1986
jiest1986
jiest1986
等级：Blank
#8 得分：0 回复于： 2009-03-22 11:26:33
请先学数学
对我有用[0] 丢个板砖[0] 引用 | 举报 | 管理
Wbl314
Wbl314
Wbl314
等级：Blank
#9 得分：0 回复于： 2009-03-22 11:39:56
目的 是为了减少循环次数，提高效率
原因： 一楼正解