Error in taking input from the BufferedReader

Question

I was asked a question regarding to find the common divisors between two numbers. I was able to figure out the logical approach using " Sieve of Eratosthenes " and I was dry running my code. But my code was giving an unexpected output in the sense that it was able to figure out the no. of common divisors between two numbers. For the 1st input but for the rest it is somehow continuing with the previous value of "inner loop j" at which it was stopped for the 1st test case ; for other test cases.

Logical approach --> if a prime no. is a factor of given two nos. then we'll check that for every multiple of the prime no.(using array of primes[] and converting the value of multiple of primes[]=0 ) whether some of them are multiples of both the numbers or not and if yes then we'll increase the value by 1.

My question is - am using BufferedReader in the wrong way or there is some error in the code itself

Question Link-> https://www.geeksforgeeks.org/common-divisors-of-two-numbers/

Input Format The first line of the input contains a single integer T denoting the number of test cases.

The description of T test cases follows.

The first line of each test case contains two integers A and B .

Output Format For each test case, output the number of common divisors between the given pair on a seperate line.

Constraints 1 ≤ T ≤ 10 ^2

1 ≤ A , B ≤ 10 ^9

Example Input

3

100000 100000

12 24

747794 238336

Expected Output

36

6

2

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

My output for different values of input -

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

How can I figure out the mistake? I am new in using BufferedReader?

It's an algorithm issue. I think your resetting of primes array to all 1s should take place every time you get a new input, right after br.readLine(). Not a problem with buffered reader at all. You're not closing it properly though. Look up "try-with-resources". — julien.giband
– julien.giband, Commented Jul 1, 2021 at 8:53
Yes, I figured it out for my code to work fine I need to create new primes[] for every test case which (would be very inefficient) for very huge test cases. Thank you!! — SHIVAM TYAGI
– SHIVAM TYAGI, Commented Jul 1, 2021 at 11:01

GURU Shreyansh · Accepted Answer · 2021-07-01 09:55:53Z

1

Your algorithm is wrong. BufferedReader is working fine. Take a simple example, say a=131, b=262, your program will return 1 as an answer but the correct answer would be 2 (1 & 131). Why is this happening?
Simply because your program misses to check for all those primes which are > sqrt(min) and are factors of both numbers.
To rectify this you need to check for the divisibility with those primes in a linear manner at the end as below but this will be inefficient.

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

Also, for the correct working of above, you need to mark the i-th number as composite by primes[i]=0 during each i-th iteration.
Also, initialization of primes array should be done during each test case as in the previous testcase, the primes array would have been modified.

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

For an efficient approach, please refer to the GFG article you shared.

edited Jul 1, 2021 at 9:55

answered Jul 1, 2021 at 9:35

GURU Shreyansh

9091 gold badge9 silver badges19 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

SHIVAM TYAGI Over a year ago

Yes, I figured it out for my code to work fine I need to create new primes[] for every test case which (would be very inefficient) for very huge test cases.

Collectives™ on Stack Overflow

Error in taking input from the BufferedReader

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related