java - 找到一个至少有 100 位长且包含 273042282802155991 的素数

Question

我是 Java 的新手，我的类作业之一是找到一个至少 100 位长的质数，其中包含数字 273042282802155991。

到目前为止我已经有了这个，但是当我编译并运行它时，它似乎处于连续循环中。

我不确定我是否做错了什么。

public static void main(String[] args) {
    BigInteger y = BigInteger.valueOf(304877713615599127L);
    System.out.println(RandomPrime(y));
}

public static BigInteger RandomPrime(BigInteger x)
{
    BigInteger i;

    for (i = BigInteger.valueOf(2); i.compareTo(x)<0; i.add(i)) {
        if ((x.remainder(i).equals(BigInteger.ZERO))) {
            x.divide(i).equals(x);
            i.subtract(i);
        }
    }
    return i;
}

Answer 1

因为这是作业...

1. BigInteger 上有一个方法可以测试素数。这比尝试分解数字要快得多。 (如果您采用涉及尝试对 100 位数字进行因式分解的方法，您将失败。因式分解被认为是一个 NP 完全问题。当然，没有已知多项式时间解决。)

2. 问题是要求一个素数，当它表示为十进制数字序列时，它包含给定的数字序列。

3. 生成“随机”素数然后测试它们是否包含这些数字的方法是不可行的。 (一些简单的高中数学告诉你随机生成的 100 位数字包含给定 18 位序列的概率是...... 82/10¹⁸。你还没有测试素数...

4. 但还有另一种方法...想想吧!

只有当您在脑海中弄清楚您的算法将如何工作并进行心理估计以确认它会在合理的时间内给出答案后，才开始编写代码。

---

_{当我说不可行时，我的意思是对您来说不可行。如果有足够多的计算机、足够的时间和一些高性能数学，可能可以做其中的一些事情。因此，从技术上讲，它们可能在计算上是可行的。但它们作为家庭作业练习是不可行的。我相信这个练习的目的是让你思考如何以聪明的方式做到这一点......}