4

任务是找到 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。我做错了什么？

4

1 回答 1

3

问题是

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

计算结果为 2147483646 而不是 2147483647。

处理整数时不要使用浮点数学。在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结果）。

对于较大的指数（尽管这仅与使用BigIntegers 相关 - 在标准库中有自己的实现 - 或模幂），通过重复平方取幂

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

会带来很大的性能优势。

于 2012-12-10T23:04:16.440 回答