java - 我真的不明白我的讲师在这里说的是什么——关于用 Java 计算素数的讲义

Question

A naive algorithm for computing primenumbers exists. For example, you coulduse a while loop to check that c % i!= 0 for all positive integer i suchthat i > 1 and i < c.

However, it isnot dicult to see that a much bettermethod is making sure that c % p != 0for all prime numbers p such that p <c. Using the primes in your ArrayListthis is easy as pie. Note again thatthis suggests that you use a whileloop.

我已经尝试实现这两种方法，当我得到第一个时，检查 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;
}

虽然有效，但效率极低。我正在使用该函数创建一个素数数组列表(如果该函数返回 true，则该数字将添加到数组列表中)。

Answer 1

好吧，既然你正在创建一个包含所有素数的列表，那么当你检查数字 c 是否为素数时，你已经拥有了所有较小的素数你的 list 。对吧？

因此，不是测试小于 candidateNo/2 的任何数是否整除你的候选人，而是只测试是否有任何素数小于 candidateNo/2 candidateNo/2 划分你的候选人。

因此，您不是从 i = 2 到 candidateNo/2 迭代，而是迭代数组列表的元素。为此，这个数组列表当然应该可以从您的 isPrime 函数访问，因此要么将其作为参数传递，要么将其作为主类的公共(public)静态元素。