C++研究

Ｃ++细节深度探索及软件工程
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  37 随笔 :: 0 文章 :: 74 评论 :: 0 Trackbacks
How can you efficeny judge whether the num is primer?
A friend ask me 'How can you efficeny judge whether the num is primer? '

There is a easy way to do it , the follow code isn't written by me  but  a classic method

E.G quote from STL tutorial reference
#include <iostream>
#include <list>
#include <algorithm>
#include <cstdlib> //for abs()
using namespace std;
//predicate, which returns whether an integer is a prime number
bool isPrime (int number)
{
//ignore negative sign
number = abs(number);
// 0 and 1 are prime numbers
if (number == 0 || number == 1) {
return true;
}
//find divisor that divides without a remainder
int divisor;
for (divisor = number/2; number%divisor != 0; --divisor) {
;
}
//if no divisor greater than 1 is found, it is a prime number
return divisor == 1;
}


posted on 2007-04-19 02:39 常兴龙 阅读(317) 评论(1)  编辑 收藏 引用 所属分类: Algorithm

评论

# re: How can you efficeny judge whether the num is primer? 2008-07-05 16:31 我们一起来提高
我的看法：
（1）0和1都不算素数。
（2）2和3都是素数，可以直接返回。
（3）判断一个比较小的数（可以认为在long范围内的吧，如果是1024二进制位的大数就得想别的办法了）是不是素数肯定得穷举，提高效率就得根据已知的条件缩小穷举的空间。我认为以上程序的穷举空间还不够小。
其实只要对大于3的数num穷举从2～sqrt(num)就够了，而不用扩展到num/2。假如判断1122是不是素数，只需要穷举1122对2~33这个范围的余数有没有为0的就可以，超过33的数，如果正好有另一个积数，那么这个积数一定小于sqrt(num)，乘法运算是对称的，这是数实际上已经穷举过了。这样以1122为例就少穷举了528次，效率提高了约17倍，而这个num越大，效率提高就越明显。

不知道我说的对不对，请大家指教啊。
  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


>　hi的博客