爪哇 - 梅森素数分配

的任务是找到所有的梅森与对< = 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.我做错了什么？

来源

2012-12-10 venta7

你有非常奇怪的素数检查算法。你应该检查sqrt（数字）不超过数字/ 2 –

什么是梅森素数？ –

@SamIam：你试过Google搜索吗？有一个专门用于梅森素数的网站（http://www.mersenne.org/），维基百科和MathWorld都有关于它们的信息。 – mellamokb

的问题是，

(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结果）。

对于较大的指数（尽管这仅是相关使用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; 
}

会给一个大的性能优点。

来源

2012-12-10 23:04:16

我仍然处在本书的开头（第5章方法），它应该尽可能地写出与本书涵盖的内容一样多的代码。我已经尝试过（长）（Math.pow（2，数字）也没有成功 – venta7

所以没有位移？ –

不知道如何与他们合作，我正在寻找这个位移谷歌现在，但它不应该使用它们，虽然谢谢你的帮助 – venta7

爪哇 - 梅森素数分配

回答

相关问题