这是一个获取质数的代码,我已经使它尽可能地高效,但是问题是,只要不能容纳那么多的信息,我就无法将其转换为BigInteger;这里的代码:
public class p3{
static long perfectNumber;
static long mersenne;
public static void main(String[] args) {
long p = 2;
while (true) {
if( p % 2 == 0&&p!=2){
p++;
}
else{
if (isPrime(p) == true) {
mersenne = (long) (Math.pow(2, p) - 1);
if (isPrime(mersenne) == true) {
perfectNumber = (long) Math.pow(2, (p - 1)) * mersenne;
System.out.println(perfectNumber);
}
}
p+=1;
}
}
}
private static boolean isPrime(long testPrime) {
for (long i = 3; i < Math.sqrt(testPrime); i += 2) {
if (testPrime % i == 0) {
return false;
}
}
return true;
}
}
我尝试使用BigInteger,但是代码无法正常工作,因为我无法使用带有pow的BigInteger指数
您不需要。指数不必与mersenne素数和完美数一样大。他们可以有自己独立的isPrime()
测试。实际上,它们必须是int
而不是long
才能满足BigInteger.pow()
。
以下是您要的,但可能不是您想要的。我怀疑由于时间限制,您是否会在原始代码之外再得到一个完美的数字,这就是@WJS将您推向另一个方向的原因。
import java.math.BigInteger;
public class p3 {
static BigInteger TWO = new BigInteger("2");
static BigInteger THREE = new BigInteger("3");
public static void main(String[] args) {
int p = 2;
while (true) {
if (isPrime(p)) {
BigInteger mersenne = TWO.pow(p).subtract(BigInteger.ONE);
if (isPrime(mersenne)) {
System.out.println(TWO.pow(p - 1).multiply(mersenne));
}
}
p += (p == 2) ? 1 : 2;
}
}
private static boolean isPrime(BigInteger number) {
if (number.mod(TWO).equals(BigInteger.ZERO)) {
return number.equals(TWO);
}
for (BigInteger i = THREE; number.compareTo(i.multiply(i)) >= 0; i = i.add(TWO)) {
if (number.mod(i).equals(BigInteger.ZERO)) {
return false;
}
}
return true;
}
private static boolean isPrime(int number) {
if (number % 2 == 0) {
return number == 2;
}
for (int i = 3; number >= i * i; i += 2) {
if (number % i == 0) {
return false;
}
}
return true;
}
}
输出
> java p3
6
28
496
8128
33550336
8589869056
137438691328
2305843008139952128
2658455991569831744654692615953842176
您的原始代码输出0代替上面的最终(37位)数字。因此,当前的问题确实是long
无法容纳足够的信息。但除此之外,您根本无法使用上述算法进行足够快的计算。
如果我们对上面的代码做一些简单的事情,例如替换此行:
if (isPrime(mersenne)) {
with:
if (mersenne.isProbablePrime(10)) {
该代码将先吐出前20个完美数字,然后再缓慢爬行。根据需要调整isProbablePrime()
的certainty参数。