Java - 梅森素数赋值

Question

任务是找到所有 p <= 31 的梅森素数并显示在表格中:

p     2^p-1
---   ---- 
2      3

3      7

5      31

...

到目前为止我的结果是这段代码:

public class PE28MersennePrimeVer2 {

    public static void main(String[] args) {

        System.out.println("p\t2^p - 1");

        for (int number = 2; number <= 31; number++) {
            if (isPrime(number)) {
                int mersennePrime = (int)(Math.pow(2, number)) - 1;
                if (isPrime(mersennePrime)) {
                    System.out.print(number + "\t" + mersennePrime + "\n");
                }
            }
        }
    }

    public static boolean isPrime(int number) {

        if ((number == 1) || (number == 2)) {
            return true;
        }

        for (int i = 2; i <= number/2; i++) {
            if (number % i == 0) {
                return false;
            }
        }

        return true;
    }
}

p 的输出最多为 19，永远不会达到 31。我做错了什么？

Answer 1

问题是

(int)Math.pow(2,31) - 1;

评估为 2147483646 而不是 2147483647。

处理整数时不要使用 float 学。在 Java 中，使用 (1 << number) - 1有效(1 << 31 由于溢出在 C 中是未定义的行为，但它是在 Java 中定义的)。

如果您不能使用移位，您可以编写自己的整数幂函数。对于所考虑的小指数，直接

long pow(long base, long exponent) {
    long result = 1;
    while(exponent > 0) {
        result *= base;
        --exponent;
    }
}

足够好(注意:我使用 long 而不是 int 来避免溢出；虽然溢出行为是在 Java 中定义的，但避免溢出更干净)。

这样，

mersennePrime = (int)(pow(2,number) - 1);

完成它的工作(尽管您应该考虑将 long 也用于其他变量，而不仅仅是中间 pow 结果)。

对于较大的指数(尽管这只与使用 BigInteger 相关 - 在标准库中有自己的实现 - 或模幂)，通过重复平方求幂

long pow(long base, long exponent) {
    long aux = 1;
    while(exponent > 0) {
        if (exponent % 2 == 1) {
            aux *= base;
        }
        base *= base;
        exponent /= 2;
    }
    return aux;
}

会带来很大的性能优势。