计算最多N个整数的素数

我正在尝试自己编写一个小脚本来计算所有素数到n（用户提交的参数），并希望得到一些帮助。 我想使用ArrayLists来编写这个函数，并希望尽可能高效 – 对于我来说，我似乎无法掌握的另一件大事就是做所有标准和良好实践（即用大写字母等等） ）所以，如果你不介意，请指出这方面的任何错误，以便我可以解决它们。

这是我到目前为止编写的代码，但我知道有很多方法可以优化它 – 具体来说，我有一个布尔数组存储数字是否为素数。 当然有一个更好的方法来做这个，而不是循环通过数组并使一切都是素数，然后摆脱不是的数字？

非常感谢你的时间！ 🙂

（tl; dr – 将脚本编写到计算机素数最多为N.我希望使用ArrayLists来执行此操作。如何使我的代码更好 – 特别是低效的布尔数组）。

import java.util.*; public class Prime { public static void main( String[] args ){ } public static void prime( int initialCapacity){ int index=0; ArrayList listOfPrimeNumbers = new ArrayList( ); 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检查器。

Answer 2

我想使用ArrayLists来编写这个函数，并希望尽可能高效。

实际上， boolean[]对于此应用程序而言比ArrayList 更有效。 一系列布尔占用较少的空间，操作更快。 （如果需要List或者如果需要类似数组的数据结构，则可以在向元素添加元素时增加ArrayList 。）

对我来说另一件我无法理解的重要事情就是做一切标准和良好的做法（即用大写字母等等），所以如果你不介意，请指出这方面的任何错误，这样我就可以解决它们。

我可以做得更好。 这是原始Sun Java风格指南的链接。

当然有一个更好的方法来做这个，而不是循环通过数组并使一切都是素数，然后摆脱不是的数字？

我想您可以将数组更改为“非素数”数组，并依赖于将boolean数组初始化为所有false的事实。 但这会使代码有点扭曲。

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

Answer 3

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

解决方案：您需要关注的主要优化领域是“数字筛”。 这是一种确定数字本身的方法。 目前不可能将筛子变成单个表达式以确定它是否为素数，因此您必须努力快速消除。 这是因为除法和乘法是您可以执行的两个最昂贵的算术函数。 尽可能无需这样做可以节省您最多的时间。 以下是素数的一些基本规则（有些似乎很明显）。

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

    if（（i && 1）== 1）//主要候选人 

• 如果数字不能被任何先前的素数整除，则该数字是素数。 换句话说，您只需要使用已经找到的素数进行检查。

    for（currentOri in listOfPrimes）{
   if（i mod currentPrime == 0）{
       //不是Prime：退出For循环
   }
   } 

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

   if（（i && 1）== 1）{
   threshHold =（int）（i / 3）;  //所以你不必继续重新调整
   isPrime = true;  //假设为真，除非另有说明
   for（currentOri in listOfPrimes）{
       if（（i mod currentPrime）== 0）{
           isPrime = false;  //标记为非素数
          打破;  //提前退出For Loop
       }
       if（currentPrime> threshHold）{
          打破;
       }
   }
   if（isPrime）{
       //记录新的Prime
   }
   } 

ArrayList：关于您的ArrayList，最有效的优化方法是不存储您不需要的信息。 因为（根据你的描述）你正在寻找素数，而不是非素数，存储一个布尔ArrayList来确定它是否是素数不是你最好的选择。

仅存储您找到的素数会更有效，因为列表中不存在的任何素数肯定是非素数。 毕竟，一个数字是素数，或者不是，所以如果在列表中那么它是素数，如果不是，那么它不是。 这是特别正确的，因为你的数字筛只应该只检查先前确定的素数，无论如何。 这导致对ArrayList的写入较少，整体上的元素较少。 此外，您强制推断仅存储素数会使您的布尔值始终等于true，这意味着无需检查它。

因此我的建议是：将您的ArrayList更改为整数（或长整数）并将其用于validation和输出，因为它可用于两种目的。 有许多有效的方法可以根据此调整输出，因此这不会对您产生任何限制。 确定给定数字是否为素数（给定列表）的附加函数则很简单，即使给定ArrayList也是如此。

FuzzicalLogic

Answer 4

愚蠢的解决方案。

 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 primes = new ArrayList(); for (int i = 0; i < n; i++) { if (!notPrime[i]) { primes.add(i+1); } } 

Answer 5

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

尽管如此，在我意识到你在做什么之前，你试图使用的算法是我要建议的算法。 它很好很简单。 您可以优化它以提高效率; 不需要乘法。

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

 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 6

您当前的解决方案看起来非常破碎，如果我没有弄错，将会进入无限循环。 您可以通过移动线isPrimeNumber[index] = true;轻松修复它isPrimeNumber[index] = true; 在while循环之外（参见下面的[1]），即在开始时将0和1之外的所有内容初始化为true ，并从index=2 ，否则你将把所有内容都设置为false因为所有内容都是1的倍数。你所实现的是被称为Eratosthenes的Sieve 。 您可以使用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... }