2

我是 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;
}
4

3 回答 3

4

一个提示是这些语句什么都不做:

x.divide(i).equals(x);
i.subtract(i);

for循环的一部分相同:

i.add(i)

它们本身不会修改实例,而是返回新值——您无法检查和执行任何操作的值。 BigIntegers是“不可变的”。它们无法更改 - 但可以对其进行操作并返回新值。

如果你真的想做这样的事情,你必须这样做:

i = i.add(i);

i另外,你为什么要减去i?你不会总是期望这是 0 吗?

于 2011-12-10T02:26:56.613 回答
4

因为这是家庭作业...

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

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

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

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

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


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

于 2011-12-10T02:30:25.940 回答
0

您需要实现/使用 miller-rabin 算法

应用密码学手册

第 4.24 章 http://www.cacr.math.uwaterloo.ca/hac/about/chap4.pdf

于 2011-12-10T02:50:10.317 回答