java计算素数，最多N个整数

Question

我正在尝试自己编写一个小脚本来计算n（用户提交的参数）以下的所有素数，如果您能提供一点帮助，我将不胜感激。我想使用ArrayList来编写这个函数，并希望使它尽可能高效-对我来说，另一件我似乎无法掌握的事情是，按照标准和良好实践（即使用大写字母的类等）来做每件事，因此如果您不介意，请指出这方面的任何错误，以便我可以修复它们

这是我到目前为止写的代码，但我知道有很多方法可以优化它——特别是，我有一个布尔数组来存储一个数字是否为素数。当然有更好的方法来实现这一点，而不是在数组中循环并使所有元素都为素数，然后去掉不为素数的数字

非常感谢您抽出时间！：）

（tl；dr-编写一个脚本到N以下的计算机素数。我希望使用ArrayList来实现这一点。如何使我的代码更好-特别是效率低下的布尔数组）

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

这个答案分为两部分：素数解算器（数字筛）和包含数字的数组

解算器： 你需要关注的主要优化领域是你的“数字筛”。这就是确定一个数本身就是素数的方法。目前不可能将筛选转化为单个表达式来确定它是否为素数，因此必须努力快速消除。这是因为除法和乘法是两种最昂贵的算术函数。尽可能省去这项工作将为你节省最多的时间。下面是素数的一些基本规则（有些可能看起来很明显）

• 如果一个数是偶数（可被2整除），它就不能是素数。最快的检查方法是：

  if ((i && 1) == 1) //prime candidate

• 如果一个数不能被之前的素数整除，那么它就是素数。换句话说，你只需要使用你已经找到的素数进行检查

  for (currentPrime in listOfPrimes) {
  if (i mod currentPrime == 0) {
      //not Prime: Exit For loop
  }
  } 

• 你只需要在你正在检查的当前i的1/3上检查之前的素数（你已经移除了可被2整除的素数）
• 当然，还有一些其他的小优化，但这些是其中的大部分（目前）。这是从上面调整的for循环

  if ((i && 1) == 1) {
  threshHold = (int)(i / 3); //So you don't have to keep recalcing
  isPrime = true; //Assume true until told otherwise
  for (currentPrime in listOfPrimes) {
      if ((i mod currentPrime) == 0) {
          isPrime = false; //Flag as non prime
          break; //Exit For Loop early
      }
      if (currentPrime > threshHold) {
          break;
      }
  }
  if (isPrime) {
      //Record new Prime
  }
  }

ArrayList: 对于ArrayList，优化它的最有效方法是不存储不需要的信息。因为（根据您的描述）您正在寻找素数，而不是非素数，所以存储一个布尔数组列表以确定它是否为素数不是您的最佳选择

只存储你找到的素数会更有效，因为列表中没有的东西肯定是非素数。毕竟，一个数字要么是素数，要么不是素数，所以如果在列表中，那么它是素数，如果不是，那么它不是。这是特别正确的，因为你的数字筛应该只检查与之前确定的素数，无论如何。这会减少对ArrayList的写入，总体上减少元素。此外，您只存储素数的强制推理使您的布尔值始终等于真值，无需检查它

因此，我的建议是：将ArrayList更改为integer（或long），并将其用于验证和输出，因为它同时用于这两个目的。有很多有效的方法可以根据这一点调整你的产出，所以这不会以任何方式限制你。确定给定数字是否为素数（给定列表）的附加函数很简单，即使给定了ArrayList

模糊逻辑

Answer 2

这看起来不应该正常工作。你告诉它每个数字都是一个带isPrimeNumber[index] = true的素数，然后检查isPrimeNumber[index]是否为真；很明显，这将是因为你刚刚把它设置为真

不过，在我意识到你在做什么之前，你试图使用的算法就是我要建议的算法；这很好，也很简单。不过，你可以优化它以提高效率；不需要乘法

这里有一些伪代码可以帮助你

make a new int[initialCapacity] // or boolean[]

for i = 0 to initialCapacity-1
    array[i] = 1 // or = i, or whatever, even i+2 and you could start iterating next loop at 0
/* optionally, you can skip the above step and rely on the fact that all values will
    default to 0/false, and you can treat 0/false as prime and >0/true as not prime */

for i = 2 to initialCapacity-1
    if array[i] = 0 continue
    i is prime, do something with it here
    for j = i+i to initialCapacity-1 step i
        array[i] = 0

它使用加法而不是乘法遍历数组。这里的主要区别是，它检查当前的数字是否为素数，然后对其进行操作，而不是说“这是素数，既然我已经声明它为素数，那么我已经声明它为素数了吗？现在将其视为素数，并进一步减少该集。”此外，你需要确保不将该集减少到1，这就是为什么你跳过1，从2开始

Answer 3

I want to use ArrayLists to write this function, and hopefully make it as efficient as possible.

实际上，对于这个应用程序，boolean[]比ArrayList<Boolean>更有效。一系列布尔运算占用更少的空间，运算速度更快。（如果需要List，或者需要一个类似数组的数据结构，它可以随着元素的添加而增长，那么ArrayList更好。）

another big thing for me that I can't seem to grasp is doing everything as is standard and good practice (i.e having classes in capital letters, etc) so if you wouldn't mind please point out any mistakes in that regard so I can fix them.

我可以做得更好。这里是原始Sun Java Style Guide的链接

Surely there is a better way of doing this than cycling through the array and making everything prime, then getting rid of the numbers that are not?

我想你可以把数组改成一个“非素数”数组，并且依赖于一个boolean数组被初始化为all false的事实。但这让代码有点扭曲

还可以用int[]替换boolean[]，并使用移位/屏蔽来设置/清除单个位。这将允许您使用相同的内存量筛选更多的素数，但不一定会使程序运行得更快

Answer 4

您当前的解决方案看起来非常糟糕，如果我没有弄错的话，它将进入一个无限循环。您可以通过将isPrimeNumber[index] = true;行移动到while循环之外（参见下面的[1]）来轻松修复它，即在开始时将除0和1之外的所有内容初始化为true，然后从index=2开始，否则您将把所有内容设置为false，因为所有内容都是1的倍数。你所实现的被称为Sieve of Eratosthenes。使用Sieve of Atkins可以稍微提高效率，但这可能超出了您的能力范围

[1]为了解释我将行移到while循环之外的意思（同时我也将切换到更合适的for循环）：

for (int i = 0; i <= initialCapacity; i++)
  isPrimeNumber[i] = true;
for (int index = 0; index <= initialCapacity; index++) {
  if (isPrimeNumber[index]) {
  // rest of code here...
}

Answer 5

您可以设置listOfPrimeNumbers的初始容量，因为您可以估计N以下的素数数量。请参阅

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

但基本上n/（ln）应该是primenumbers列表的初始容量。这将确保您的程序不会不断调整封面下的列表，这可能会很昂贵

也就是说，如果你真的想提高效率。如果你不在乎，那就把列表的初始容量设置为更高的值。现在你已经将其设置为默认值，这意味着你的PrimeNumber列表将被扩展

编辑-我想你有一个错误-这行

isPrimeNumber[index] = true;

应该只在索引是质数时执行，所以将其移动到适当的if语句中。再说一遍，我不知道你的东西是怎么工作的，但我认为这是一个问题

另一种选择是使用地图作为iPrimeNumber检查器

Answer 6

一个愚蠢的解决方案

boolean[] notPrime = new boolean[n];
for (int i = 2; i <= n; i++) {
    for (int j = i * 2; j <= n; j+=i) {
        notPrime[j-1] = true;
    }
}
ArrayList<Integer> primes = new ArrayList<Integer>();
for (int i = 0; i < n; i++) {
    if (!notPrime[i]) {
        primes.add(i+1);
    }
}