求质数的优化算法示例

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);
}

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

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

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

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

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

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

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++;
      }
    }
} 

不知道对不对


具体应该问大法师啊

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

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

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

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

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