从缓冲读取器获取输入时出错

Question

有人问我一个关于找到两个数字之间的公约数的问题。我能够使用">埃拉托色尼筛"找出逻辑方法，并且我正在干运行我的代码。但是我的代码给出了一个意想不到的输出，因为它能够找出否。两个数字之间的公约数。对于第一个输入，但对于其余输入，它以某种方式继续使用"内部循环 j"的先前值，在该值处，它在第一个测试用例中停止;对于其他测试用例。

逻辑方法--> 如果质数号。 是给定两个否的因数。 然后我们将检查素数号的每个倍数。(使用 primes[] 数组并转换素数 []=0 的倍数的值)无论其中一些是否是两个数字的倍数，如果是，那么我们将值增加 1。

我的问题是 - 我以错误的方式使用 BufferedReader 或代码本身存在一些错误

问题链接-> https://www.geeksforgeeks.org/common-divisors-of-two-numbers/

输入格式 输入的第一行包含单个整数 T 表示测试用例的数量。

的描述 T 测试用例如下。

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

输出格式对于每个测试用例，在单独的行上输出给定对之间的公约数。

约束 1 ≤ T ≤ 10 ^阿拉伯数字

1 ≤ 一个 , B ≤ 10 ^9

例 输入

3

100000100000

12 24

747794 238336

预期输出

36

6

阿拉伯数字

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

我怎样才能找出错误？我是使用缓冲阅读器的新手吗？

Answer 1

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

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

此外，为了正确工作，您需要在每次i-th迭代期间通过primes[i]=0将i-th号标记为复合.
此外，primes数组的初始化应该在每个测试用例中完成，就像在之前的测试用例中一样，primes数组将被修改。

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

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