打印所有 Prime、Sophie Germain Prime、Twin Prime 和 Mersenne Prime 数字 1 到 1000000 的代码

Question

我编写了一个代码，可以测试一个数字是否是素数、索菲·杰曼素数、孪生素数和/或梅森素数。我需要将其制作成一个新代码来测试 0-1000000 的所有数字并打印出属于这些类型的每个数字。这是我需要更改的原始程序

import java.util.Scanner;
public class PrimeMethodsDemo_slm {
    public static boolean isPrime (int n) {
        boolean isPrime = true;
        if (n < 2) isPrime = false;
        else if (n == 2) isPrime = true;
        else for (int i = 2; i < Math.sqrt(n) + 1; ++i) {
            if (n % i == 0) return false;
        }
        return isPrime;
    }
    
    public static boolean isSophieGermainPrime (int n) {
        boolean isPrime = true;
        if (n < 2) isPrime = false;
        else if (n == 2) isPrime = true;
        else for (int i = 2; i < Math.sqrt(n) + 1 & (i < Math.sqrt(n * 2 + 1) + 1);
            ++i)
        {
            if (n % i == 0) return false;
        }
        return isPrime;
    }
    
    public static boolean isTwinPrime (int n) {
        boolean isPrime = true;
        if (n < 2) isPrime = false;
        else if (n == 2) isPrime = true;
        else for (int i = 2; i < Math.sqrt(n) & i < Math.sqrt(n + 2) + 1; ++i) {
            if (n % i == 0) return false;
        }
        return isPrime;
    }
    
    public static boolean isMersennePrime (int n) {
        boolean isPrime = true;
        if (n < 2) isPrime = false;
        else if (n == 2) isPrime = true;
        else
            for (int i = 2; i < Math.sqrt(n) + 1 & i < Math.sqrt(2 * n - 1) + 1; ++i)
            {
                if (n % i == 0) return false;
            }
        return isPrime;
    }
}

Answer 1

我将从简化

isPrime(int n)

方法开始。以下是我的简化解决方案：

public static boolean isPrime (int n) {
    if (n < 2) return false;
    BigInteger bigInt = BigInteger.valueOf(n);
    return bigInt.isProbablePrime(100);
}

据我了解，如果数字一开始就是质数，其余方法根据定义都是正确的。因此，这些方法中的每一个都必须检查给定的数字

n

是否是质数。如果给定的数字不是素数，您想早点返回。否则，您想继续计算以查看给定的数字是否为 Sophie Germain、Twin 或 Mersenne 素数。因此，这些方法中的每一个都应该在继续计算之前调用

isPrime(int n)

。例如，

public static boolean isSophieGermainPrime (int n) {
    return isPrime(n) && isPrime(2*n + 1);
}

public static boolean isTwinPrime (int n) {
    return isPrime(n) && (isPrime(n + 2) || isPrime(n - 2));
}

最后，您需要包含一个

main

方法，该方法可迭代范围内的所有数字，并打印出某个数字是否为素数、Sophie Germain、Twin 和/或 Mersenne 素数。

public static void main (String[] args) {
    System.out.printf("%15s | %6s | %16s | %5s | %9s |%n", "Number", "Prime?", "Sophie Germain?", "Twin?", "Mersenne?");
    for (int i = 1; i <= 1000000; i++) {
        System.out.printf("%15d | %6b | %16b | %5b | %9b |%n", i, isPrime(i), isSophieGermainPrime(i), isTwinPrime(i), isMersennePrime(i));
    }
}

显然，向控制台输出一百万行可能不是正确的做法。相反，我建议使用文件编写器并将每一行输出到文件中（除非特定要求是转储到控制台）。问题是，除非您更改控制台使用的缓冲区的大小，否则您将丢失大量输出。

如果您决定使用我的

main

方法，输出将如下所示（显示的 Mersenne 布尔值可能不正确）：

Number | Prime? |  Sophie Germain? | Twin? | Mersenne? |
     1 |  false |            false | false |     false |
     2 |   true |             true | false |      true |
     3 |   true |             true |  true |      true |
     4 |  false |            false | false |     false |
     5 |   true |             true |  true |      true |
     6 |  false |            false | false |     false |
     7 |   true |            false |  true |      true |
     8 |  false |            false | false |     false |
     9 |  false |            false | false |     false |
    10 |  false |            false | false |     false |
    11 |   true |             true |  true |     false |
    12 |  false |            false | false |     false |
    13 |   true |            false |  true |      true |
    14 |  false |            false | false |     false |
    15 |  false |            false | false |     false |
    16 |  false |            false | false |     false |
    17 |   true |            false |  true |      true |
    18 |  false |            false | false |     false |
    19 |   true |            false |  true |      true |
    20 |  false |            false | false |     false |
    21 |  false |            false | false |     false |
    22 |  false |            false | false |     false |
    23 |   true |             true | false |     false |
    24 |  false |            false | false |     false |
    25 |  false |            false | false |     false |
    26 |  false |            false | false |     false |
    27 |  false |            false | false |     false |
    28 |  false |            false | false |     false |
    29 |   true |             true |  true |     false |
    30 |  false |            false | false |     false |
    31 |   true |            false |  true |     false |

更新： OP 评论道“主要方法有效，但是我只需要它打印出每种类型的质数......”

使用我的解决方案并遵守此要求的一种潜在方法是简单地指示您的循环打印您想要的内容。例如，要打印 Sophie Germain 素数，只需执行以下操作：

public static void main (String[] args) {
    System.out.printf("%10s%n", "Sophie Germain Primes");
    for (int i = 1; i <= 1000000; i++) {
        if (isSophieGermainPrime(i)) {
            System.out.printf("%7d%n", i);              
        }
    }
}

这将输出类似的内容

Sophie Germain Primes
      2
      3
      5
     11
     23
     29
     41
     53
     83
     89
    113
    131
    ...

根据 Wolfram MathWorld 网站

，上面显示的顺序是正确的

Answer 2

虽然不是 OP 目标的直接一部分，但有些性能改进。

使用整数解决整数问题

代码可以通过简单地比较除数和商来避免类型转换和浮点

Math.sqrt(n)

。

// i < Math.sqrt(n) + 1
i <= n/i    // Is the divisor <= to the quotient? 

测试 Even 很简单

考虑使用简单的

n % 2 == 0

这允许循环使用

+= 2, rather than 

++` 更快地迭代。

简化

public static boolean isPrime (int n) {
  if (n % 2 == 0) return n == 2;
  for (int divisor = 3; divisor <= n / divisor; divisor += 2) {
    if (n % divisor == 0) return false;
  }
  return n > 1;  // Fail for n as 1, 0 or any negative.
}

效率：我希望一步计算出

n/divisor

和附近的

n % divisor

。

---

先测试素数

由于任何非素数也不是 Sophie Germain Prime、Twin Prime 或 Mersenne Prime，因此请考虑不要调用

isSophieGermainPrime()

、

isTwinPrime()

、Mersenne Prime，除非

isPrime(n)

为 true。 那么这些作为局部函数，甚至不需要对其进行

isPrime(n)

测试。 此外，我会将先前的素数传递给

isTwinPrime()

，以用比较替换

isPrime(n-2)

测试。

梅森素数也是一个梅森数。 ：

n

是一个梅森数，带有简单的逻辑测试：

(n & (n+1)) == 0

。

---

高级

要了解真正的改进，请参阅埃拉托斯特尼筛法。