java - 请帮助...我在 Java 中计算素数的实现是否在做它应该做的事情？

Question

有人向我描述了我将如何使用 Java 实现质数生成器；但我不确定我是否做对了。我希望有人能给我一些关于如何改进我的实现的一般性建议!请不要给我答案，因为这是家庭作业，我想自己解决这个问题/成为一个更好的程序员/不作弊!

我将在下面发布描述和我的解决方案，基本上我只是想知道一些一般性的事情 - 我是否正确地遵循了说明(最重要的是我发现使用的语言有点困惑)以及我是否可以制作我的程序任何更好的(如果是的话，一些一般性的提示会很好，这样我就可以弄清楚如何......我认为我对对数的使用已经过时了，但我想不出更好的方法来使用它)!

如果这是不允许的，我们深表歉意 - 如果不允许，请忽略或删除!非常感谢您的帮助! :)

描述:

Prime( int initialCapacity ): The class constructor. The purpose of the constructor is to compute and store the first initialCapacity prime �first initialCapacity primefirst initialCapacity primefirst i numbers. The idea is that you compute the numbers once and store them so that you can re-use them several times. You should use an ArrayList to store the prime numbers. An algorithm for computing prime numbers is provided in the next section.

1. Start with an empty list of prime numbers. You may represent this list using an ArrayList.

2. While the size of the ArrayList is not equal to n, consider the next candidate prime number. Initially, the next candidate prime number should be 2, but otherwise it should be the successor of the previous candidate prime number.

3. If the candidate prime number is a prime then add it to the list.

4. Continue with Step 2.

Note that this algorithm suggests that you should use a while loop. Step 3 of the previous algorithm requires that you know how to decide whether a given candidate prime, c > 1, is a prime number. As a matter of fact, the de􀀀nition of prime numbers already suggests a naive algorithm. For example, you could use a while loop to check that c %i 6= 0 for all positive integers i such that 1 < i and i < c. However, it is not dicult to see that a much better method is making sure that c % p 6= 0 for all prime numbers p such that p < c. Using the primes in your ArrayList this is easy as pie.is method is the method which you are supposed to use. Note again that this suggest that you use a while loop. Finally, your implementation should be ecient and should not waste checks of the form c % p 6= 0 or c % p = 0. So, you should stop cheking as soon as c % p = 0 for some of the primes in ArrayList.

我的解决方案如下:

import java.util.*;
public class Prime {

  public static void main( String[] args ){

  }
  public static void prime( int initialCapacity){
    int index=2;
    int logOfInitialCapacity = initialCapacity / (int)(Math.log(initialCapacity));
    ArrayList<Integer> listOfPrimeNumbers = new ArrayList<Integer>(logOfInitialCapacity);
    boolean[] isPrimeNumber = new boolean[initialCapacity + 1]; // boolean defaults to
    // false

    for (int i=0;i==initialCapacity;i++) {
        isPrimeNumber[index] = true;
      }
      while ( index <= listOfPrimeNumbers.size() )
      {
        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++;
      }
  }

}

它应该计算素数的第一个 initialCapacity 并将它们保存在 arrayList 中，因为问题要求...我只是不确定我是否完全按照问题所说的那样做了。这可能更多的是整天学习和有点疲惫的产物!

非常感谢您的帮助和阅读所有这些；很抱歉发了这么长的帖子。

Answer 1

你可以这样回答你自己的问题:

http://primes.utm.edu/lists/small/1000.txt

如果这些不在您的列表中，则说明您的代码执行不正确。

你会想读这个:

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