问一个超级弱的问题，求素数中为什么要先开平方

Question

这是算法上的问题，好好考虑一下算法，还要考虑一下素数的定义。 
素数是只有1和本身能整除的整数。所以在求素数的时候，要将素数与1到素数本身中间的所有整数都相除，看是否有整除的数，如果有，那肯定不是素数了。但是从算法上考虑，为了减少重复量，开平方后面的数就不用相除了，因为a/b（平方数）=c（小一点的数），同样a/c=b。举例说明： 
25，开平方以后是5,那么整除2~5就可以了，如果有满足条件的，就是素数。 看完之后还是晕，谁能解释的再清楚一些

Answer 1

定义a=x*y (a,x,y都是正整数)
如果x和y都大于a的开平方
那么x*y>a,矛盾了.
所以必有一个数是小于等于a的开平方,如果这个数不等于1,那么a就是素数了.

Answer 2

利用数学概念降低搜索范围.如果真的存在a*b = n,其中b大于n^(1/2)那么必然有a小于n^(1/2).

Answer 3

开方是为了减少除数的量，这样大大提高除数求余效率。开平方后面的数就不用相除了，因为开方得的数是除数最大因子了。  如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;
}

Answer 4

这是输入一个数，判断有多少个素数
#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;
}

Answer 5

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