查找长度至少为 100 位且包含 273042282802155991 的素数

发布于 2024-12-20 07:08:06 字数 602 浏览 3 评论 0原文

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

原文

I am new to Java and one of my class assignments is to find a prime number at least 100 digits long that contains the numbers 273042282802155991.

I have this so far but when I compile it and run it it seems to be in a continuous loop.

I'm not sure if I've done something wrong.

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;
}

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

堇年纸鸢 2024-12-27 07:08:06

因为这是家庭作业...

BigInteger 上有一个方法可以测试素数。这比尝试对数字进行因式分解要快得多。（如果您采用尝试分解 100 位数字的方法，您将会失败。分解被认为是一个 NP 完全问题。当然，不存在已知多项式时间解决方案。）
问题要求提供一个素数，该素数包含给定的数字序列（当它表示为十进制数字序列时）。
生成“随机”素数然后测试它们是否包含这些数字的方法是不可行的。（一些简单的高中数学告诉你，随机生成的 100 位数字包含给定的 18 位数字序列的概率是 ... 82 / 10¹⁸。而且你还没有测试素性...
但是还有另一种方法可以做到这一点...考虑一下！

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

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

回复收藏 0 原文

提笔落墨 2024-12-27 07:08:06

一个提示是这些语句不执行任何操作：

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

与 for 循环的一部分相同：

i.add(i)

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

如果你真的想做这样的事情，你必须这样做：

i = i.add(i);

另外，为什么要从 i 中减去 i？你不是一直期望这个值为 0 吗？

One tip is that these statements do nothing:

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

Same with part of your for loop:

i.add(i)

They don't modify the instances themselves, but return new values - values that you're failing to check and do anything with. BigIntegers are "immutable". They can't be changed - but they can be operated upon and return new values.

If you actually wanted to do something like this, you would have to do: