素数测定的一般方法
2013年09月16日
⁄ 综合
⁄ 共 2588字 ⁄ 字号
小 中 大
一． 试除法
bool IsPrime( unsigned n )
...{
if ( n < 2 )
...{ // 小于2的数即不是合数也不是素数
throw 0;
}
for ( unsigned i = 2; i < (int) ceil( sqrt(n) ) ; i++ )
...{ // 和比它的平方根相除，如果都除不尽，证明素数
if ( 0 == n % i )
...{ // 除尽了，合数
return false;
}
}
return true; // 都没除尽，素数
}
二． 建立素数表
一个合数必然可以由两个或多个质数相乘而得到。那么如果一个数不能被比它的一半小的所有的质数整除，那么比它一半小的所有的合数也一样不可能整除它。建立一个素数表是很有用的。
bool IsPrime2( unsigned n )
...{
if ( n < 2 )
...{ // 小于2的数即不是合数也不是素数
throw 0;
}
static unsigned aPrimeList[] = ...{ // 素数表
1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 113,
193, 241, 257, 337, 353, 401, 433, 449, 577, 593, 641,
673, 769, 881, 929, 977, 1009, 1153, 1201, 1217, 1249,
1297, 1361, 1409, 1489, 1553, 1601, 1697, 1777, 1873,
1889, 2017, 2081, 2113, 2129, 2161, 2273, 2417, 2593,
2609, 2657, 2689, 2753, 2801, 2833, 2897, 3041, 3089,
3121, 3137, 3169, 3217, 3313, 3329, 3361, 3457, 3617,
3697, 3761, 3793, 3889, 4001, 4049, 4129, 4177, 4241,
4273, 4289, 4337, 4481, 4513, 4561, 4657, 4673, 4721,
4801, 4817, 4993, 5009, 5153, 5233, 5281, 5297, 5393,
5441, 5521, 5569, 5857, 5953, 6113, 6257, 6337, 6353,
6449, 6481, 6529, 6577, 6673, 6689, 6737, 6833, 6961,
6977, 7057, 7121, 7297, 7393, 7457, 7489, 7537, 7649,
7681, 7793, 7841, 7873, 7937, 8017, 8081, 8161, 8209,
8273, 8353, 8369, 8513, 8609, 8641, 8689, 8737, 8753,
8849, 8929, 9041, 9137, 9281, 9377, 9473, 9521, 9601,
9649, 9697, 9857
};
const int nListNum = sizeof(aPrimeList) / sizeof(unsigned);
for ( unsigned i = 2; i < nListNum; ++i )
...{ // 和比它小的所有的数相除，如果都除不尽，证明素数
if ( n / 2 + 1 < aPrimeList[i] )
...{ // 一定是素数了
return true;
}
if ( 0 == n % aPrimeList[i] )
...{ // 除尽了，合数
return false;
}
}
for ( unsigned i = aPrimeList[nListNum - 1]; i < n / 2 + 1; i++ )
...{ // 真不幸，遇到了这么大的素数
if ( 0 == n % i )
...{ // 除尽了，合数
return false;
}
}
return true;
}