java - 计算最多 N 个整数的素数

Question

我正在尝试自己编写一个小脚本来计算最多为 n(用户提交的参数)的所有素数，希望能提供一点帮助。我想使用 ArrayLists 来编写这个函数，并希望尽可能提高它的效率——对我来说另一件我似乎无法理解的大事是按照标准和良好做法做所有事情(即用大写字母等来上课) ) 因此，如果您不介意，请指出这方面的任何错误，以便我进行修复。

这是我到目前为止编写的代码，但我知道有很多方法可以优化它 - 具体来说，我有一个 boolean 数组存储一个数字是否为素数。肯定有比循环遍历数组并使所有素数都为素数，然后去掉不是素数的数字更好的方法吗？

非常感谢您的宝贵时间! :)

(tl;dr - 编写一个脚本来计算最多 N 个素数。我希望使用 ArrayLists 来执行此操作。我怎样才能使我的代码更好 - 特别是低效的 boolean 数组)。

import java.util.*;
public class Prime {

  public static void main( String[] args ){

  }
  public static void prime( int initialCapacity){
    int index=0;
    ArrayList<Integer> listOfPrimeNumbers = new ArrayList<Integer>( );
    boolean[] isPrimeNumber = new boolean[initialCapacity + 1]; // boolean defaults to
    // false
    while ( index <= listOfPrimeNumbers.size() )
    {
      isPrimeNumber[index] = true;
      if (isPrimeNumber[index]) {
        listOfPrimeNumbers.add(index);
      }
      for (int j = index; j * index <= initialCapacity; j++) {
        isPrimeNumber[index * j] = false;
      }

      // Now mark the multiple of i as non-prime number
      index++;
    }
  }

}

Answer 1

你可以设置listOfPrimeNumbers的初始容量，因为你可以估计N以下有多少素数。见

http://en.wikipedia.org/wiki/Prime_number_theorem

但基本上 n/(ln n) 应该是 listOfPrimeNumbers 的初始容量。这将确保您的程序不会在幕后不断调整列表的大小，这可能代价高昂。

也就是说，如果你真的想要高效。如果您不在乎，则只需将该列表的初始容量设置为更高的值。现在您已将其设置为默认值，这意味着您的 listOfPrimeNumbers 将会扩展。

编辑 - 我认为你有一个错误 - 该行

isPrimeNumber[index] = true;

只应在 index 为质数时执行，因此将其移至适当的 if 语句中。再一次，我不知道你的东西是如何工作的，但我认为这是一个问题。

另一种方法是使用 Map 作为 isPrimeNumber 检查器。