Yime limits excceds for test case 0

#1

import java.util.*;
public class Main {
public static void main(String args[]) {
Scanner sc= new Scanner(System.in);
int n= sc.nextInt();
int a[][] = new int[n][2];
for(int i=0;i<n;i++){
for(int j=0;j<2;j++){
a[i][j]= sc.nextInt();
}
}
for( int i=0;i<n;i++){
int np =0;
for (int j= a[i][0];j<=a[i][1];j++){
if(prime(j))
np++;
}
System.out.println(np);

}


}
public static boolean prime(int a) {
	
	if(a<2)
		return false;
	for(int i=2;i*i<=a;i++) {
		if(a%i==0) {
			
			return false;
		}
	}
	return true;
}

}
Please suggest a more optimized method so that I can compute fore test case 0

#2

@Vishu_1801
you dont need a 2d array to compute the primes.preprocess ur sieve array and store number of primes from 1 to i at index i.
refer to this…your rpime function is right
Scanner scn = new Scanner(System.in);
int t = scn.nextInt();
while (t-- > 0) {
int a = scn.nextInt(), b = scn.nextInt();

        int[] prime = new int[b + 1];
        prime[0] = 0;
        prime[1] = 0;

        for (int i = 2; i <= b; i++) {
            if ((i & 1) == 0 || i < a) {
                prime[i] = 0;
            } else {
                prime[i] = 1;
            }
        }
        if (2 >= a) {
            prime[2] = 1;
        }
        for (int i = 3; i <= b; i += 2) {

            int j = 2;
            while (i * j <= b) {
                prime[i * j] = 0;
                j++;
            }
        }

        int count = 0;
        for (int i = 0; i <= b; i++) {
            if (prime[i] == 1) {
                count++;
            }
        }

        System.out.println(count);
    }
#3

Do we first need to give all input before displaying output as here you took one input and displayed the output before taking input for other test case??

#4

Also i am unable to get your code please please explain ?

#5

what is the work of the second for loop

#6

Why have we started checking prime from 2 onward only when we can start from a

#7

what does i & 1 do??

#8

@Vishu_1801 yes, we take input for first case ,then print the output then take another input

#9

@Vishu_1801 The & operator provides a mask that “cancels out” bits in the first depending if they’re set in the second parameter - so assume N is the number 17, that expressed in binary is 00010001, the number 1 in binary is 00000001, so masking the two together will “blank” the first set of bits, leaving you with N as 00000001.

Basically that particular if statement drops all except the last bit, which is either 0 or 1, so it is a condition detecting if N is even or odd
eg 101&1==1 5 is odd

#10

@Vishu_1801 in the first loop we marked all evens and all the numbers smaller than a as not prime .else prime
in that case we wd have marked 2 as nit prime so we marked it prime
in the third loop we marked all the multiples of odds as not prime
and we can start checking from a .thats right