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

Question

我正在尝试解决 SPOJ 中的“素数生成器”，使用 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，而是返回一个新的 BigInteger。

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

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

<小时/>

底线:在将代码发布到 StackOverflow 之前，请尝试调试您的代码。
使用您选择的 IDE。
这种错误确实会发生，但如果您调试代码并无意识地单步执行程序，直到您想知道为什么它还没有前进，那么它们很容易被缓存。