ACM/ICPC 2009 合肥现场赛 Mersenne Prime 题解
这道题认真做起来确实比较复杂，要求判断梅森素数。
梅森素数其实比较少，可以说少得还挺可怜的。数据范围是 1 到 257. 而且本题的最大数 2257 的位数也不多，而且其中没有多少素数。但是如果用打表，那就水了。
但是如果不打表，要用到高精度；不仅用到高精度，还要用到大素数的判断。这样的话传统的素数判定是不行的，要用到 Miller-Rabin 算法的高精版本。
最后我采取了一种……略无耻的做法，就是——用 Java!
这个问题上，Java 的好处就是封装了高精类，而且它居然也有 Miller-Rabin 算法。Java 的文档中说，如果迭代 k 次，那么那个算法正确的概率是 [latex]1 – (\frac{1}{2})^{k}[/latex]. 那么考虑到要判断 257 个数，我要让错误的概率在 [latex]\frac{1}{257}[/latex] 左右，我就果断迭代了 8 次。
代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | import java.util.*; import java.math.*; public final class Main { private static BigInteger one = BigInteger.ONE; private static BigInteger two = new BigInteger("2"); private static BigInteger[] M = new BigInteger[258]; private static boolean[] isPrime = new boolean[258]; public static void main(String[] args) { M[0] = one; for (int i = 1; i < 258; ++i) M[i] = M[i - 1].multiply(two); for (int i = 0; i < 258; ++i) M[i] = M[i].subtract(one); for (int i = 0; i < 258; ++i) isPrime[i] = M[i].isProbablePrime(8); // for (int i = 0; i < 258; ++i) // System.out.println(M[i] + ":" + (isPrime[i] ? "Prime" : "NotPrime")); Scanner cin = new Scanner(System.in); while (cin.hasNext()) { int n = cin.nextInt(); if (n == 0) break; System.out.println(n + ":" + (isPrime[n] ? "Prime" : "NotPrime")); } } } |
