我真的不明白我的讲师在这里得到了什么 - 关于用Java计算素数的讲义

Question

存在用于计算素数的朴素算法.例如,您可以使用while循环来检查所有正整数i的c%i!= 0,使得i> 1且i <c.

然而,不难看出更好的方法是确保所有素数p的c%p!= 0,使得p <c.使用ArrayList中的素数这很容易.请再次注意,这表明您使用while循环.

我试图实现这两种方法,当我得到第一个,检查c%i!= 0时,我不明白第二条信息说更好的算法是使用c%p! = 0.这不意味着我必须知道计算素数的所有素数吗？

我现在所拥有的内容如下:

  public static void isPrime(int candidateNo) {
while (i <= candidateNo/2) {
  if (candidateNo%i==0 && i!=1) {
    return false;
  }
  else
    return true;
}

}

哪个有效,但效率低下.我正在使用该函数创建素数的arraylist(如果函数返回true,则将数字添加到arraylist中).

Answer 1

好吧,既然您正在创建所有素数的列表,那么当您检查数字c是否为素数时,您的列表中已经包含所有较小的素数.对？

因此,不测试是否有任何小于candidateNo/2您的候选人的数字,您只测试是否有任何素数小于candidateNo/2您的候选人.

因此,不是迭代,而是迭代i = 2 to candidateNo/2数组列表的元素.为此,当然可以从isPrime函数访问此数组列表,因此要么将其作为参数传递,要么将其作为主类的公共静态元素.