从BufferedReader获取输入时出错

Question

有人问我一个关于求两个数之间的公约数的问题。我能够使用“埃拉托色尼筛”找出逻辑方法，我正在运行我的代码。但是我的代码给出了一个意想不到的输出，它能够计算出no。指两个数之间的公约数。对于第一个输入，但对于其余的输入，它以某种方式继续与前一个值“内部循环j”，在该值处，它在第一个测试用例中停止；对于其他测试用例。

逻辑方法-->如果一个素数不。是给定两个NO的因子。然后，我们将检查每一个素数的倍数。（使用素数组[]并将素数的倍数转换为[]=0)是否有一些是这两个数的倍数，如果是，那么我们将值增加1。

每个测试用例的第一行包含两个整数A和B。

输出格式对于每一个测试用例，输出给定对之间的公因子数在一个分离的线上。

约束条件1≤T≤10^2

100000 100000

12 24

747794 238336

try{
        
        long primes[]=new long[1000005];
                for(int i=2;i<=100000;i++){
                        primes[i]=1;
                }
                BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                int t = Integer.parseInt(br.readLine());
                for(int k=0;k<t;k++){
                        String s = br.readLine();
                        String s2[] = s.split(" ");
                        long a = Long.parseLong(s2[0]);
                        long b = Long.parseLong(s2[1]);
                        
                        long min = Math.min(a,b);
                        long max= Math.max(a,b);
                        System.out.println("Value of max = "+max);
                        System.out.println("Value of min = "+min);
                        long count=1;
                        for(int i=2;i*i<=min;i++){
                                if(primes[i]==1){
                                    System.out.println("Value of i = "+i);
                                        if(max%i==0 && min%i==0){
                                                count++;
                                        }
                                        for(int j=i;j*i<=min;j++){
                                                if(primes[i*j]==1){
                                                   
                                                        primes[i*j]=0;
                                                         System.out.println("Value of j = "+j);
                                                        if((max%(i*j)==0) && (min%(i*j)==0)){
                                                            
                                                                count++;
                                                        }
                                                }
                                        }
                                }
                        }
                        System.out.println(count);
                }
    }catch(Exception e){
        return;
    }
    

Value of max = 24
Value of min = 12
Value of i = 2
Value of j = 2
Value of j = 3
Value of j = 4
Value of j = 5
Value of j = 6 <------
Value of i = 3
Value of j = 3
6
Value of max = 40
Value of min = 20
Value of i = 2
Value of j = 7  <------
Value of j = 8
Value of j = 9
Value of j = 10
Value of i = 3
Value of j = 5
3
Value of max = 100
Value of min = 20
Value of i = 2
Value of i = 3
2

我怎样才能找出错误呢？我刚开始使用BufferedReader？

Answer 1

你的算法错了。BufferedReader工作正常。举一个简单的例子，比如a=131，b=262，程序将返回1作为答案，但正确的答案是2(1&131)。为什么会出现这种情况？
只是因为您的程序没有检查所有素数，这些素数是>sqrt(min)并且是这两个数字的因子。
要纠正这种情况，您需要在末尾以线性方式检查这些素数的可除性，如下所示，但这将是低效的。

for (int i=2; i<=min; i++)
    if (primes[i] == 1 && (max%(i)==0) && (min%(i)==0))
        ++count;

此外，为了正确地执行上述操作，您需要在每次I-迭代期间将I-编号标记为由Primes[i]=0合成。
此外，Primes数组的初始化应该在每个测试用例期间进行，因为在前面的测试用例中，Primes数组将被修改。

primes[] = new long[1000005];
    for(int i=2; i<=100000; i++)
        primes[i] = 1;

有关有效的方法，请参阅您共享的GFG文章。