如何在 JAVA 中为 (2^(n-1) mod 1 =1) 保留更大的值

Question

我正在尝试解决 SPOJ 中的 "prime generator"，使用 2^(n-1)%n==1 找到素数，但对于整数来说它变得更大，在某些时候很长，因此我试过 BigInteger，即使现在它也没有显示输出。

我已经尝试过其他各种技术，但很明显超过了时间限制，想尝试除SOE算法之外的其他方法。

import java.io. * ;
import java.math. * ;
import java.util. * ;
import java.util.Scanner;

class Scratch {
    public static void main(String[] args) {
        Scanner in =new Scanner(System. in );
        int t = in.nextInt();
        for (int i = 0; i < t; i++) {
            BigInteger a = in.nextBigInteger();
            BigInteger b = in.nextBigInteger();
            for (BigInteger j = a; j.compareTo(b) < -1; j.add(BigInteger.ONE)) {
                BigInteger n = j;
                BigInteger r = new BigInteger("2");
                int wow = n.intValue();
                BigInteger y = r.pow(wow - 1);
                System.out.println(y);
                if ((y.mod(n)).compareTo(BigInteger.ONE) == 0)
                    System.out.println(j);
            }
        }
    }

现在不显示任何输出。

Answer 1

在您的 for 循环中，您不会递增 j。

for (BigInteger j = a; j.compareTo(b)<-1; 
                 j.add(BigInteger.ONE)) {

j.add(...) 不会更改 j，而是 returns 一个新的 BigInteger。

要修复您的代码，只需将 j.add(BigInteger.ONE) 的结果分配给 j:

for (BigInteger j = a; j.compareTo(b)<-1; 
                 j = j.add(BigInteger.ONE)) {

底线：请在将代码发布到 Whosebug 之前尝试调试代码。
使用您选择的 IDE。
这种错误会发生，但如果您调试代码并且只是盲目地逐步执行程序，直到您想知道为什么它还没有前进，它们很容易被缓存。

如何在 JAVA 中为 (2^(n-1) mod 1 =1) 保留更大的值

How to hold greater values for (2^(n-1) mod 1 =1) in JAVA

java

int

biginteger