素数相关类设计

Question

我正在创建一个类，它应该包含与素数相关的所有方法。现在，我必须实现一个方法isPrime()来检查一个数字的素数。我必须用两种方式来实现它，一种是使用以氏筛，另一种是使用标准的循环。类的创建方式应该是，如果我使用特定的构造函数来实例化它，那么它就应该使用筛子算法。如果我使用另一个构造函数，那么它应该使用寻找素数的标准方法(通过循环)。现在，我在考虑概念亲和力的情况下做出了这个实现。我创建了内部类来实现这两种类型的实现。这是最好的方法吗，还是我应该使用单独的类？

import java.util.Arrays;

/**
 * Class for Prime Number related methods.
 */
public class PrimeNumber {

    private PrimeAbstract primeNumber;

    /**
     * If you want the class to use <code><b>sieve of erastosthene</b></code> as the
     * base algorithm then you need to use this constructor. You need to pass the
     * limit till which you want the sieve to be initialized as the method parameter.
     * @param limit
     */
    public PrimeNumber(int limit) {
        this.primeNumber = new PrimeNumberWithSieve(limit);
    }

    /**
     * If you want the class to use the classic way of finding out the primality
     * of a number. By classic we mean for looping.
     */
    public PrimeNumber(){
        this.primeNumber = new PrimeNumberClassic();
    }

    /**
     * Returns if a number is prime or not.
     * @param number
     * @return boolean
     */
    public boolean isPrime(int number){
        return primeNumber.isPrime(number);
    }



}

/**
 * abstract class of prime number object
 */
abstract class PrimeAbstract {

    public abstract boolean isPrime(int number);
}




/**
 * This class uses <code><b>sieve of erastothene</b></code> as the base
 * algorithm for finding out the primality of a natural number.
 */
class PrimeNumberWithSieve extends PrimeAbstract {

    boolean[] sieve;

    public PrimeNumberWithSieve(int limit){
        sieve = limit<1000?new boolean[1001]:new boolean[limit+1];
        Arrays.fill(sieve, true);
        sieve[0]=sieve[1]=false;
        for (int i=2;i<sieve.length;i++) {
            if(sieve[i]) {
                for (int j=2;i*j<sieve.length;j++) {
                    sieve[i*j]=false;
                }
            }
        }
    }

    /**
     * This method returns if a number is prime or not.
     * It uses the sieve of erastothene method to figure this out.
     * The sieve is declared in the class and initialized on instantiating
     * the class.
     * @param number
     * @return
     */
    public boolean isPrime(int number){
        return sieve[number];
    }
}

/**
 * This class uses standard for looping for finding out the primality of a number.
 */
class PrimeNumberClassic extends PrimeAbstract{

    public PrimeNumberClassic(){
    }

    /**
     * This method returns if a number is prime or not.
     * It uses the classical style of for looping through all the numbers
     * till the <b>sqaure root</b> of the number.
     * @param number
     * @return
     */
    public boolean isPrime(int number) {
        if (number%2==0) return false;
        for(int i=3;i*i<=number;i+=2) {
            if(number%i==0)
                return false;
        }
        return true;
    }

}

Answer 1

Bugs in PrimeNumberClassic

这个类中有多个bug:2不是素数，而任何<=到1的数字都被认为是素数:(

一些大的数字可能会导致无限循环！(在我的文章末尾，我将详细介绍这方面的情况)

在考虑我的其他评论之前，您应该：

• 纠正它们
• 在某些情况下(2，多偶数而不是2，3，5，7，31,277，一些非常大的数字和负数)，对两个类进行单元测试(检查JUnit)。

考虑使用更大的数字

int没有那么大，如果你打算做数学计算，你应该考虑改用long或BigInteger。

现在，真正的评论是：

对PrimeNumber

的评述

我不太明白这门课是怎么回事。名字听起来像是在存储素数，但不是.它看起来就像某种工厂。

我会考虑删除它，除非您想要添加更多的功能(在这种情况下，这可能是未来的对象，后续，问题^)。

对PrimeAbstract

的评述

/**
 * abstract class of prime number object
 */
abstract class PrimeAbstract {

    public abstract boolean isPrime(int number);
}

为什么这是abstract class？它显然是一个interface，而且javadoc也是非常无用的。

名字不是很好..。为什么是PrimeAbstract？PrimeNumberFinder/ PrimeNumberDetector名称是否更接近意图？

原始抽象的儿童

综述

实现中的代码确实需要呼吸！

在里面放一些空格;)从现在开始读起来很累人。

根据经验，在= (以及+= ofc之类的东西)之间放置空格，“？”符号和它们的操作数，以及比较器和它们的操作数之间。

if (number%2==0) return false;

我是不关心在非常简单的情况下使用{的人之一.然而，如果把回报放在同一条线上，就很难读懂国际海事组织。

正如在其他问题中所说的，任何好的IDE都有一个代码格式化程序，包括解决以前的所有问题(以及自动缩进代码)；

筛子是奥基什..。我不太喜欢这样一个事实，即当您使用isPrime的数字太大时，它会异常失败。此外，您还应该使字段private ;)

我可能会让筛子变懒，直到第一次调用isPrime时才计算它。

1000是一个神奇的数字，应该变成一个常数。

最后，将每个结果存储在一个数组中实际上是没有效率的。也许只考虑将素数存储到HashSet中，带有HashSet的contains方法非常快。

我会优化PrimeNumberClassic以：

• 了解一些非常小的素数的结果(降低“常见”情况的复杂性)
• 最多只能有一平方米的数字..。是的，我知道你已经用我*我这么做了，但它不太清楚，不太可能表现，它是错误的(如果我变大，它会溢出，你会发现自己有一个潜在的无限循环或访问的索引不在你的数组中.没有好处)

因此，最终，这个实现可能看起来类似于：

public boolean isPrime(final int number) {
    if (number == 2) {
        return true;
    } else if (number % 2 == 0) {
        return false;
    } else if (number < 36) {
        return number == 3 || number == 5 || number == 7 || number == 11 || number == 13
                || number == 17 || number == 19 || number == 23 || number == 29 || number == 31;
    }

    final int max = (int) Math.round(Math.sqrt(number));
    for (int i = 3; i <= max; i += 2) {
        if (number % i == 0)
            return false;
    }
    return true;
}

Answer 2

1. 在我的同类类中，我发现nextPrime(int num)和previousPrime(int num)是有用的，前者比第二个有用。它们分别返回下一个高素数和下一个下素数。
2. 使用布尔数组对空间的使用效率极低。最好使用BitSet，它每个数字只使用一位。只需在筛子中保存奇数，你就可以通过额外的编码，将每个数字减少到一半。
3. 您的PrimeNumberClassic.isPrime()不能将2标记为素数。

下面是一个更好的版本，代码中有更多空格，以便更容易阅读：

public boolean isPrime(int number) {
    if (number < 2) {
        return false;
    }
    if (number % 2 == 0) {
        return number == 2;  // 2 is the only even prime.
    }
    for (int i = 3; i * i <= number; i += 2) {
        if (number % i == 0) {
            return false;
        }
    }
    return true;
}

如果你准备好了筛子，那么你可以用类似的方法来测试筛的极限和它的正方形之间的数字：

for (int i = 3; i * i <= number; i = sieve.nextPrime(i)) {
    if (number % i == 0) {
        return false;
    }
}

这使用了我前面建议的nextPrime()方法，并且避免了像15或27这样的奇数合成数的除法。