回归自然！-算法问题大挑战寻找质数

让我们暂时忘了EJB,STRUTS,Web Service这种虚妄的大东西吧！让我们挑战一下计算的本质！

要求：

给出一个程序用于寻找质数。尽可能优化程序，使得计算速度更快。

我先抛砖引玉，给出一个最直接的算法。此算法只有最起码的优化。

/**
* 寻找用户给定的两个整数之间所有的质数。命令行:java PrimeLister [下限] [上限]
*
* @author Alienbat
*
*/
public class PrimeLister
{

public static void main(String[] args)
{
long startValue = 1;
long endValue = -1;

if (args.length == 0 || args.length > 2)
{
System.out.println("[start value] [end value(optical)]");

return;
}
else if (args.length == 1)
{
startValue = Long.parseLong(args[0]);
System.out.println(
"start value: " + startValue + ", no end value!");
}
else if (args.length == 2)
{
startValue = Long.parseLong(args[0]);
System.out.println("start value: " + startValue);
endValue = Long.parseLong(args[1]);
System.out.println("end value: " + endValue);
}

long num = startValue;
if (num % 2 == 0)
{
num++;
}

//---------------------------------以上是读取用户输入数字的部分
//---------------------------------以下是计算并显示质数的部分

while (endValue < 0 || num < endValue)
{
for (long i = 3; i < num; i = i + 2)
{

if (num % i == 0)
{
break;
}
else if (i == (num - 2))
{
System.out.println(num);
}
}
//只计算奇数
num = num + 2;

//去除尾数为5的数
if (num % 5 == 0)
{
continue;
}
}
}
}

简单的优化有：
只检测一个奇数是否是质数。忽略偶数。
忽略尾数为5的数。（因为尾数为5则肯定能被5整除）。

-----------------------------
期望大家贴出更有效的算法。Don't let me down!

90 个解决方案

#1

首先一个最大的改进，

for (long i = 3; i < num; i = i + 2)

-->

long sqrtNum = (long)(Math.sqrt(num) + 1)

for (long i = 3; i < sqrtNum; i = i + 2)
就可以了，

检查一个数A是否是质数，只要从3往上+2看能否整除，直到这个的平方根

因为如果一直到Sqrt(A)一直没有能整除的话，检查超过Sqrt的部分也是没有必要的，那个肯定是个质数。

这样改进之后的算法复杂度，降低很多

#2

还有一个比较快的算法，就是每次尝试整除的不是3, 5, 7, 9, 11, 13, 15

而是2, 3, 5, 7, 11, 13, 17, 19也就是小于SQRT(A)的所有质数

因为如果C < B < SQRT(A) , and C is a Prime, B % C == 0 的话，

且 A % C != 0，那么 A % B 肯定也 != 0

#3

对不起，纠正一下，上面提到的都是小于等于SQRT(A)

#4

#5

根据shine333(enihs)给出的算法，速度有了极大的提高。

在我的P4 1.8G机器上，
使用原来的算法寻找1~50000内的质数，耗时6.4秒。
使用平方根算法寻找1~50000内的质数，耗时0.28秒。

以下是新算法的代码：
while (endValue < 0 || num < endValue)
{
//平方根算法
long sqrtNum = (long) (Math.sqrt(num) + 1);

inner:for (long i = 3; i <= sqrtNum; i = i + 2)
{

if (num % i == 0)
{
break inner;
}
else if (i == sqrtNum||i==sqrtNum -1)
{
System.out.println(num);
}
}
//只计算奇数
num = num + 2;

//去除尾数为5的数
if (num % 5 == 0)
{
continue;
}
}
----------------------------
另外，你提出的后一种算法我没试过。不过我觉得如果那样算的话，则还需要计算SQRT(A)以内的质数，可能反而增加了运算时间。

#6

public class Test{
  public static void main(String[] args){
    int begin = Integer.parseInt(args[0]);
    int end = Integer.parseInt(args[1]);
    long l1 = System.currentTimeMillis();
    boolean flag[] = new boolean[++end];
    flag[0] = flag[1] = flag[2] = true;
    int limit = (int)Math.sqrt(end);
    for (int j=3; j<=limit; j+=2){
      if (flag[j] == false){
        for (int i=j+j; i<end; i+=j){
          flag[i] = true;
        }
      }
    }
    System.out.println("Used:"+(System.currentTimeMillis()-l1));
    /*
    System.out
            .println("Prime Numbers from " + begin + " to " + (end-1) + ":");
    if(begin%2 == 0)begin++;
    for(int i=begin; i<end; i+=2){
      if(flag[i] == false){
        System.out.print(i + ",");
      }
    }*/
  }
}

#7

果然不错。。。。

#8

> 另外，你提出的后一种算法我没试过。不过我觉得如果那样算的话，则还需要计算SQRT(A)以内的质数，可能反而增加了运算时间。

那些质数你只需要计算一次，每次发现一个，就把它登记在册，以后就不需要重复计算的。
比如，你现在的上限args[1] = 50000，也就是SQRT(A) = 224，大致相当于你要尝试112个奇数，而224以内的质数显然只有几十个。而每一个num你都能节省那么多次计算，何乐而不为呢？而且，这个args[1]越大，有时越明显。

当然如果args[1]过小的话，比如 < 1000的话，可能没有直接从args[0]开始计算来的快。

所以，可能需要添加一个判断，什么范围用质数的查找，什么时候，直接从3开始+2

另外，如果偷懒一点，把所有100以内的质数作为已知条件的话，速度更快（但不明显）。

#9

有一本英文的研究生教材<计算机算法>

里面有讲解这一内容的

#10

shine333(enihs)
把已经运算出来的质数存储起来，用作除数来判断新的质数。这个算法应该很快，但略有点复杂。等我写出程序再贴出来。

先贴出使用平方根算法结果：

Search prime ranged from 1 to 10000000 cost time: 105.852 second(s)

#11

使用存储质数的算法有个和算法无关的问题，可能会影响效率。

在java中能够存储原生值的容器只有数组，但是数组的大小是不可变的，因此无法满足需要。其他可变长度容器都只能容纳对象。如果使用包装类，则内存分配会在堆中，可能会影响效率。另外我不知道大量对象会不会导致内存不足。

#12

以下是存储质数算法。只贴出运算部分。

Vector primes=new Vector();
primes.add(new Long(3));

while (endValue < 0 || num < endValue)
{
long sqrtNum = (long) (Math.sqrt(num) + 1);

boolean foundPrime=false;

inner:for (Iterator iter=primes.iterator();iter.hasNext();)
{
long i=((Long)iter.next()).longValue();

if (num % i == 0||i>sqrtNum)
{
break inner;
}
else if (i == sqrtNum||i==sqrtNum -1)
{
foundPrime=true;

System.out.println(num);
}
}
if(foundPrime){
primes.add(new Long(num));
foundPrime=false;
}
//只计算奇数
num = num + 2;

//去除尾数为5的数
if (num % 5 == 0)
{
continue;
}
}

结果：
Search prime ranged from 5 to 10000000 cost time: 46.346 second(s)

快了很多。但是有个bug，运算到8468077就停止了，没有继续查找剩余质数。不知道程序中有什么缺陷。

#13

值得一顶,

#14

平方根算法是计算质数的经典算法,很多计算机教材中都有提到!

#15

#16

关注

#17

int sqrtValue;
boolean isPrime;
for (int i=(startValue%2==0)?startValue+1:startValue; i<=endValue; i+=2) {
    if (i%5 ==0) {
        continue;
    }
    isPrime = true;
    sqrtValue = Math.sqrt(i) + 1;
    for (int j=3; j<=sqrtValue; j++) {
        if (i%j == 0) {
            isPrime = false;
            break;
        }
    }
    if (isPrime) {
        System.out.println(i + " is prime.");
    }
}

#18

study

#19

让我尝试一下，不过，在关于算法的方面，质数查找和平方根的运用应该是我所知最快的算法了

#20

不错，多几个这样的贴子才有价值

#21

//去除尾数为5的数
if (num % 5 == 0) {
continue;
}

这句应该放到刚进入 while 的地方
放到底下不紧啥用没有, 而且还增加一定开销

#22

这个本来就是放到while里面的阿

#23

恩
本来看到一开始的程序就想回平方根的做法
不过一楼看来很快，到二楼基本上就补充完整了

说一些我的看法，大质数的算法是一个世界性的难题。至今（包括我所看到的研究）应该说都是递推算法。也就是说必须要知道前面的质数才能判断后面那个是不是质数。

我所能看到的最好的算法是不必一个个的递推，而是知道前几个可以跳过几个知道后面那个是不是质数。

shine333(enihs) 的回答很正确，个人认为这个问题并不是一个算法问题，而是一个数学问题。

ps:应该用数组来做

#24

package function;

public class PrimeSeeker {

  static class LongList {
    long[] elements;

    int count;

    public LongList() {
      this(10);
    }

    public LongList(int initCapacity) {
      elements = new long[initCapacity];
    }

    public int size() {
      return count;
    }

    public void add(long value) {
      if (count >= elements.length) {
        long[] newElements = new long[elements.length << 1];
        System.arraycopy(elements, 0, newElements, 0, count);
        elements = newElements;
      }

      elements[count++] = value;
    }

    public LongIterator iterator() {
      return new LongIterator() {
        int index;

        public boolean hasNext() {
          return index < count;
        }

        public long next() {
          return elements[index++];
        }
      };
    }
  }

  static interface LongIterator {
    boolean hasNext();

    long next();
  }

  public static LongList seekPrime(long maxValue) {
    LongList primeList = new LongList( (int) (maxValue >> 4) + 10);

    primeList.add(2);

    for (long num = 3; num <= maxValue; num += 2) {

      //Square root
      long sqrt = (long) (Math.sqrt(num) + 1);

      boolean isPrime = true;

      for (LongIterator iter = primeList.iterator(); iter.hasNext(); ) {
        long div = iter.next();

        if (div >= sqrt) {
          //This is a prime
          continue;
        }

        if (num % div == 0) {
          //Not a prime
          isPrime = false;
          break;
        }
      }

      if (isPrime) {
        primeList.add(num);
      }

    }

    return primeList;
  }

  public static void main(String[] args) {
    long maxValue = Long.parseLong(args[0]);

    long startTime = System.currentTimeMillis();

    LongList primeList = seekPrime(maxValue);

    long endTime = System.currentTimeMillis();

    System.out.println("Time Cost: " + (endTime - startTime) + "ms");

    System.out.println("Total Found: " + primeList.size());

  }
}

这里的改进，在算法上没什么改进

随便跑了几遍，发现用直接存放long的容器，比存放Long的java.util.Collection快很多，而且发现一个的规律，质数的个数，大致是maxValue的1/10不到一点，所以，我的初始容器大小，定在了maxValue的1/16左右，省得多次的内存分配，当然，在运行的时候，指定了-Xms -Xmx参数。

另外，我还没有试过1000000以上的数字。

另外，我曾尝试了类似双向冒泡排序的算法，将maxValue也逐步往下减，但发现效果并不好。

#25

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class PrimeExplorer {
    public static void main(String[] args) throws IOException {
        int startValue;
        int endValue;
        int n;
        int sqrt;
        int divisor;
        int count;
        Prime head;
        Prime tail;
        Prime prime;
        boolean isPrime;
        BufferedReader in;

        in = new BufferedReader(new InputStreamReader(System.in));

        // Get input.
        do {
            try {
                System.out.print("From: ");
                startValue = Integer.parseInt(in.readLine());
                System.out.print("To:   ");
                endValue = Integer.parseInt(in.readLine());
                // Start from 11.
                if (startValue < 11 || endValue <= startValue) {
                    continue;
                } else {
                    break;
                }
            } catch (NumberFormatException e) {
                continue;
            }
        } while (true);

        n = startValue;
        // Start from even.
        if (n % 2 == 0) {
            n++;
        }
        count = 0;

        // Prepare all prime numbers in 10 except 1.
        head = new Prime(5);
        head.next = new Prime(3);
        head.next.next = new Prime(7);
        prime = head;
        tail = head.next.next;

        //========================================
        long startTime = System.currentTimeMillis();

        for (isPrime = true; n < endValue;
                n += 2, prime = head, isPrime = true) {

            sqrt = (int) Math.sqrt(n) + 1;

            // Find prime number.
            for (divisor = prime.value; prime.next != null;
                    prime = prime.next, divisor = prime.value) {
                if (n % divisor == 0) {
                    isPrime = false;
                    break;
                } else if (divisor > sqrt) {
                    break;
                }
            }

            // Append this prime number to the list tail.
            if (isPrime) {
                count++;
                prime = tail;
                prime.next = new Prime(n);
                tail = prime.next;
                // TODO: Uncommont this for validating result.
                //System.out.println(n);
            }
        }

        System.out.println("Total: " + count);
        long endTime = System.currentTimeMillis();
        System.out.println("cost: " + (endTime - startTime));
        //========================================
    }

    private static class Prime {
        public Prime next = null;
        public int value;

        public Prime(int value) {
            this.value = value;
        }
    }
}

平方根是个好方法
存储质数更是个好方法
但是使用数组存储质数在这里显然就不是一个好方法了
这里使用链表比较合适, 即节省空间, 而且速度更快

if (div >= sqrt) {
    //This is a prime
    continue;
}
shine333兄的问题出在这块语句
这里就算找到了质数,还是要遍历完整个数组
虽然数组里面都是质数, 数大了也受不了
相比线性探测法性能优势较弱

而链表法一可最小化使用内存资源占用,
二可客服此缺陷, 当确定 n 不是质数后立刻跳出循环
从而大大提升性能, 达到存储质数法的目的

从 11 算到 10,000,000
"开方法"耗时 70秒左右
"开方法 + 链表存储质数法"耗时 9秒左右
机器是 Athlon 2500+; 1G DDR333 RAM

#26

还有一点是
个人感觉这里没有使用 long 的必要
因为 2,000,000,000 以上的数大可交给 64bit CPU 去计算
使用 32bit CPU 计算 long 在性能上是很难令人接受的
讲上面程序里面的 int 换成 long 以后
从 11 算到 10,000,000 耗时 22秒多
性能粗略的算是降低了整一倍
以上测试均使用官方SDK
虽然不论是 int 还是 long 在算法上没区别
但是使用 long 的测试过程是在令人太难忍受了...

顺便纠正上面一个错误
"开方法"耗时 70秒左右
这个程序当时使用的是 long
换成 int 后结果变为 27秒左右

开方法:
From: 11
To: 10000000
Total: 664575
cost: 27109

开方法 + 链表存储质数法:
From: 11
To: 10000000
Total: 664575
cost: 9516

#27

好阿

#28

对不起，楼上的continue确实是错的，应为break.

#29

另外，在性能上,在32位CPU上，int和long确实是有差别的

#30

可以从小到大找，判断大的数是否素数，只要判断是否能被比较小的素数整除就行了。当然，只要判断到这个数的根号就可以了。

#31

大家应该看一下如何使用C做的

因为使用C能进行极大的优化（优化后的东西，也许根本就看不懂）
然后在翻译为java 再做优化

#32

这就是传说中的那个狂人么。

#33

如果我没看错的话，上面所有的算法都是：

foreach x from 2 to n
check x isPrime?
end

isPrime?的算法复杂度是O(n*n)，这是不用讨论的，否则RSA加密就已经没有意义了。这样一来，“求n以内的所有素数”整个算法的复杂度就是O(n*n*n)。那么，O(n*n*n)是否最低的近似算法复杂度？在做那些细节优化之前不妨先考虑这个问题。我再给个提示：答案早在两千多年前就已经有了。

#34

忙，不过值得一顶

#35

苦思不得解
还望 Schlemiel(维特根斯坦的扇子) 将这两千年前的答案赐教于我等

#36

寻找素数的经典算法是筛法，公元前250年左右由希腊数学家厄拉托塞提出的。简单描述如下：

put(2 to n) into container
foreach x = 2 to sqrt(n)
  m = 2
  while x*m <= n
    container.remove(x*m)
    m++
  end
end

先设P=2，将n以内P的所有倍数划去；再设P=3，将n以内P的所有倍数划去；如此反复直至P大于n的平方根。划剩下来的就是n以内所有的素数。这个算法的复杂度是O(n*n)。连寻找素数的基本算法是什么都没想清楚就开始写程序，真是不怕累。

#37

这个其实就是先假设所有数字都是质数，然后将较小的质数的倍数去除，
但是，这个不是个合适的计算机的算法，至少现在不是。

你考虑过存储空间吗？

算法复杂度不仅包括了时间复杂度，还包括了空间复杂度。

#38

请看楼主的题目：
“给出一个程序用于寻找质数。尽可能优化程序，使得计算速度更快。”
OK？

#39

foreach x from 2 to n
  check x isPrime?
end

这个是符合我们现在讨论的算法的，而你说的 isPrime?是O(n*n),就好像不对了

我们现在是

foreach x from 2 to n
  foreach y from 2 to min(maxKnownPrime, SQRT(x))
    if (x mod y == 0) Not Prime, quit loop
  end
end

仍然是O(n*n)吗

#40

不管你用什么算法，isPrime的判断肯定是指数时间，不可能是多项式时间。这一结论并没有得到数学上的证明，但RSA算法尚且安全，说明我们仍然可以相信这是真的。你明白我的意思吗？

#41

有一点，我不太明白，就是测试“一个”整数是否是质数的复杂度为什么会使O(n*n),

因为，最糟糕的算法，也就是从2到n-1,尝试做整除，顶多作n-2次，顶多是O(n),

而利用平方根（不考虑只用质数）的情况下，判断一个整数是否质数的复杂度为O(sqrt(n))。

由于无法知道小于n的质数的个数，那么姑且用O(sqrt(n/2))来做区分

因为专业的关系，学校里没有学过专门的课程，因而对算法的基础实在太差。还望不吝赐教

#42

由于从小学到大学数学一直没学好所以就不跟各位高人谈论复杂度问题了
下面的程序是按照 Schlemiel(维特根斯坦的扇子) 老兄的算法做的实现
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class PrimeFilter {
    public static void main(String[] args) throws IOException {
        int startValue;
        int endValue;
        int count;
        int limit;
        int factor;
        Candidate head;
        Candidate prime;
        Candidate candidate;
        BufferedReader in;
        boolean print = false;

        // Get input.
        in = new BufferedReader(new InputStreamReader(System.in));
        do {
            try {
                System.out.print("From: ");
                startValue = Integer.parseInt(in.readLine());
                System.out.print("To:   ");
                endValue = Integer.parseInt(in.readLine());
                break;
            } catch (NumberFormatException e) {
                continue;
            }
        } while (true);

        //========================================
        long startTime = System.currentTimeMillis();

        // Generate candidates.
        head = new Candidate(3);
        candidate = head;
        // Add odd only.
        for (int i = 5; i < endValue; i += 2) {
            candidate.next = new Candidate(i);
            candidate = candidate.next;
        }

        // Filter prime numbers.
        limit = (int) Math.sqrt(endValue) + 1;
        for (prime = head, count = endValue / 2;
                prime.value < limit; prime = prime.next) {
            for (factor = prime.value, candidate = prime;
                    candidate != null && candidate.next != null;
                    candidate = candidate.next) {
                if (candidate.next.value % factor == 0) {
                    count--;
                    candidate.delNext();
                }
            }
        }

        if (print) {
            for (prime = head; prime.next != null; prime = prime.next) {
                System.out.println(prime.value);
            }
        }

        System.out.println("Total: " + count);
        long endTime = System.currentTimeMillis();
        System.out.println("Cost: " + (endTime - startTime) + "ms");
        //========================================

    }

    private static class Candidate {
        public Candidate next;
        public int value;

        public Candidate(int value) {
            this.value = value;
        }

        public void delNext() {
            next = next.next;
        }
    }
}

运行结果如下:
java -Xms200m -Xmx300m PrimeFilter
From: 3
To:   10000000
Total: 664579
Cost: 45156ms

实在想不通是哪儿出问题了...

#43

.net写了一下，写法几乎和上面完全一样。
我的机器配置：xp(sp4)/PIII 1G/512M

11到10000000，一共15秒，找到664575个质数。

有点差别的地方是，使用了ArrayList，而且在存储已知质数的list中，使用了for循环而不是foreach循环（提高了12秒左右，原来是27秒）

#44

楼上的兄弟把代码贴上来看看啊

#45

試過了Schlemiel(维特根斯坦的扇子)的方法，在10000000的范围里，使用int[]，且remove操作仅仅做清0操作，快了很多。

但是想了半天，反先这个方法不是快在算法复杂度上。我感觉Schlemiel(维特根斯坦的扇子)的算法，其实就是我们原先用较小质数尝试，直到平方根的算法的另一种描述行式，两个都应该是O(n*sqrt(n))。他的方法运行起来之所以快，而是快在平时在计算算法复杂度时忽略的地方。那就是乘法和取余操作的耗时是不一样的，就好像i *= 2; 和 i <<= 1的耗时是不一样的一个道理。

package test;

public class Test {
  public static void main(String[] args) throws Throwable {

    long start = System.currentTimeMillis();
    for (int i = 0; i < 100000000; i++) {
      int x = i % (i + 100);
    }
    long end = System.currentTimeMillis();
    System.out.println(end - start);
  }

}

试了三次，分别耗时4336ms，4587ms，4437ms

而使用int x = i * (i + 100); 仅耗时681ms，641ms，651ms。

#46

#47

shine333(enihs)兄能不能把你测试代码贴上来
我想学习一下怎么实现的

#48

int[] primes = new int[maxValue - 1];

for (int i = 0; i < primes.length; i++) {
  primes[i] = i + 2;
}

int sqrt = (int) (Math.sqrt(maxValue) + 1);

for (int i = 2; i < sqrt; i++) {
  int m = 2;
  while (i * m <= maxValue) {
    primes[i * m - 2] = 0;
    m++;
  }
}

基本上就是这样子，没有仔细检查是否是该算法的正确表述。

#49

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class PrimeFilter {
    public static void main(String[] args) throws IOException {
        int startValue;
        int endValue;
        int total;
        int limit;
        int prime;
        int factor;
        int product;
        int n;
        int[] list;
        BufferedReader in;

        // Get input.
        in = new BufferedReader(new InputStreamReader(System.in));
        do {
            try {
                System.out.print("From: ");
                startValue = Integer.parseInt(in.readLine());
                System.out.print("To:   ");
                endValue = Integer.parseInt(in.readLine());
                break;
            } catch (NumberFormatException e) {
                continue;
            }
        } while (true);

        //========================================
        long startTime = System.currentTimeMillis();

        n = endValue;
        list = new int[n];
        list[0] = 0;
        list[1] = 1;
        list[2] = 2;
        total = 2;
        for (int i = 3; i < n; i += 2) {
            total++;
            list[i] = i;
        }

        limit = (int) Math.sqrt(n) + 1;
        for (prime = 3; prime < limit;) {
            // Filter non prime number.
            for (factor = prime; (product = factor * prime) < n; factor += 2) {
                if (list[product] != 0) {
                    list[product] = 0;
                    total--;
                }
            }
            // Skip non prime number.
            do {
                prime += 2;
            } while (list[prime] == 0);
        }

        // TODO: Change this flag for validating result.
        if (false) {
            System.out.println(list[1] + "\n" + list[2]);
            for (int i = 3; i < list.length; i += 2) {
                if (list[i] != 0) {
                    System.out.println(list[i]);
                }
            }
        }

        System.out.println("Total: " + total);
        long endTime = System.currentTimeMillis();
        System.out.println("Cost: " + (endTime - startTime) + "ms");
        //========================================
    }
}

我实现了一下
的确是有了质的飞跃
上面的实现可能还有可优化的地方
我们上面的算法关键问题不在 % 运算(虽然也有一定影响)
而是在开方上面
之前的算法要开方 n/2 次
而这个算法只要开一次
不过这个算法太耗费资源, 算到 2 ^ 31 需要 2G 内存
无论如何这个算法的确是非常快

#50

这个算法叫做筛子Sieve, 那个老头叫Eratosthenes.

另外用boolean[]更节约开销吧，或许也会提升速度，就好像long[] -> int[]的提升

#1

#2

#3