求质数的优化算法示例

public static void primeDemo(int N)  {

  List<integer></integer> list = new LinkedList<integer></integer>();
  list.add(2);
  for (int i = 3; i < n; i++) {
   // 偶数，就跳过，它肯定不是质数
      if (i % 2 == 0)
           continue;
   // 判断3，5，7，9……i/2是否有i的因子
       int j = 3;
       while (j <= i / 2 && i % j != 0)
            j += 2; 
   // 若上述数都不是i的因子，则i是质数
      if (j > i / 2) {
           list.add(i);
       }
  }
  for(int prime : list) 
        System.out.println(prime);
}

评论

14 楼 topkinghat 2011-09-30  

这个叫优化？哎...忽悠啊!

13 楼 fins 2006-12-27  

给楼主两个建议吧

1 以后不要起这么有"诱惑性"的标题名字
到现在我也没明白你为什么认为你那个算法是"优化"的
那不优化的算法是什么样的?遍历从2到n?
地球上任何一个小学毕业的人都不会那么做的

2 "正在学习datastructure和algorithm中" 看到这句话就不舒服
数据结构 和 算法 真的比 datastructure和 algorithm 难输入吗?
其实我老鄙视那种成天说话夹着英文的人了
一没有国外背景 二不是港澳台胞 大家都是中国人 何必呢
datastructure和algorithm 又不像 spring hibernate这类的东西是专有名词 你就直接写中文呗 
我四级才30多分 专业英语开卷 在文曲星的帮助下我才61分 :'(

以上只是些我个人的看法  没有攻击的意思
只是些建议 别多想哈

12 楼 qiezi 2006-12-26  

这个还可以再优化，只需要求模“2到'M的平方根'之间的质数”就可以了，也就是除你上面的list里面的元素，list初始时需要放入一个2，从2开始找质数，一直找到M的平方根，最后把list里面N以后的元素返回。

11 楼 pro_ygw 2006-12-26  

首先谢谢fins & ddandyy & renyangok 以及各位的热心参与,这是我第一次在JAVAEYE上发布的第一篇article,对比了你们给的建议,最后测试还是遍历2到n的平方根最为捷径(快).代码如下:
[color=violet]

public class PrimeNumberDemo{   
  public static void main(String[] args){   
   	int number = 10;// 初始化number,即[N,M]中N的值
	boolean isPrime = true;
	System.out.println("The First prime numbersare \n");
	List<Integer> list = new LinkedList<Integer>();
	while (true) {
		isPrime = true;
		int tempSqrt = (int) Math.sqrt(number);
		for (int divisor = 2; divisor <= tempSqrt; divisor++) {
			if (number % divisor == 0) {
				isPrime = false;
				break;
			}
		}
		if (isPrime) 
			list.add(number);
		number++;
		if (number >= 100000)  // 100000即代表M的值
			break;
	}
	for (int primenumber : list)
		System.out.println(primenumber);
    }   
}

[/color]
正在学习datastructure和algorithm中

10 楼 renyangok 2006-12-26  

http://www.blogjava.net/renyangok/archive/2006/11/20/82278.html
看看我转的这篇文章吧，好几种权威的方法呢

9 楼 Elminster 2006-12-25  

这个问题，好一些的做法是保存一个当前已经得到的质数列表，这样在做除法判断的时候只需要判断那些质数，而不必从 2 到 sqrt(n) 一个一个去检查。对于较大的 n ，这样做可以节省许多时间。

8 楼 fins 2006-12-25  

楼上这个算法是对的 但是应该再优化一点

for(int divisor=2; divisor<=math.sqrt(number);divisor++){
改成

int tempSqrt =(int)Math.sqrt(number);
for(int divisor=2; divisor<= tempSqrt ;divisor++){ 

这样可以避免每次循环都进行开方运算

7 楼 ddandyy 2006-12-25  

google了一下 LZ这个好像在别的地方也有  不知道是不是LZ贴过去的
另外又看到了这个

public class PrimeNumber{
  public static void main(String[] args){
    int count=1;
    int number=2;
    boolean isPrime=true;
      System.out.println("The First prime numbersare \n");
      while(count<=100){
        isPrime=true;
          for(int divisor=2; divisor<=math.sqrt(number);divisor++){ 
            if(number%divisor==0){
              isPrime=false;
              break;
             }
            }
           if(isPrime){
             if(count%10==0){
             System.out.println(number);
           }
           else
             System.out.print(number+"   ");
             count++;
           }
            number++;
      }
    }
} 

不知道对不对


具体应该问大法师啊

6 楼 fins 2006-12-25  

pro_ygw 写道

算法这个东西我还没去学过,我只是觉得现在比较方便,这个思想还是原来接触C的时候学的,要确实用算法的话,还是fins大哥说得对--遍历2到n的平方根. 请问你们有什么好的学习数据结构和算法的书籍和资料吗?

没有
我学的也不好
只是碰巧知道了求质数的一个简单的算法

5 楼 zhenyu33154 2006-12-25  

算法是什么，还不是解决问题的方法，关键是解决问题所用的方法的好坏，在算法中，对数据结构的使用比较重要，用得好，你的程序质量好效率高，用得不好，那就难说了！

4 楼 pro_ygw 2006-12-25  

算法这个东西我还没去学过,我只是觉得现在比较方便,这个思想还是原来接触C的时候学的,要确实用算法的话,还是fins大哥说得对--遍历2到n的平方根. 请问你们有什么好的学习数据结构和算法的书籍和资料吗?

3 楼 zhenyu33154 2006-12-25  

这个肯定要比那个一直遍历下去要节省资源些，因为在遇到不符合条件的就不去做，直接进入下一轮的判断。

2 楼 fins 2006-12-25  

?? 楼主 这个为什么是优化的算法呢?
我觉得比常用的算法还要慢啊
常用算法是 遍历 2 到 n的平方根
楼主的方法是遍历 2到 n/2
明显慢很多啊

1 楼 Elminster 2006-12-25  

你管这个叫优化算法？咳咳 ……