Find the probability of picking a prime number in a range The task is:

From a sub-sequence of integers between 2 inputted numbers A and B, we need to find the probability of picking a prime number. I have written something to accomplish the task-

import java.util.*;
class Sample{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int cases = sc.nextInt();
        for(int i = 0; i&lt;cases; i++){
            int l = sc.nextInt();
            int r = sc.nextInt();

            double ans = 0.0;
            for(int j = l; j&lt;=r;j++){
                if(isPrime(j)){
                    ans++;
                }
            }
            System.out.println(String.format("output: %.6f",ans/(r-l+1)));

        }

    }
    public static boolean isPrime(int n){
        boolean ans = true;
        if(n == 1){
            ans = false;
        }
        if(n&gt;5&amp;&amp; n%5==0){
            ans = false;
        }
        if(n&gt;2&amp;&amp;n%2 == 0){
            ans = false;
        }
        else{
        for(int i = 3; i&lt;(Math.sqrt(n)+1);i=i+2){
            if(n%i == 0){
                ans = false;
                break;
            }
        }}
        return ans;
    }
}


We also input an integer (cases) to represent the number of test cases.
This gives a correct answer on my machine, but gets a time limit exceeded verdict when I upload it. I thought that maybe using c++ would solve the issue.

So I made a similar program in c++, but still it does not match the time limit of 1 second. The C++ code is:

#include &lt;iostream&gt;
#include &lt;math.h&gt;
using namespace std;
bool isPrime(int n){
    bool ans= true;
    if(n == 1){
        ans = false;
    }
    if(n &gt; 2 &amp;&amp; n%2 == 0){
        ans = false;
    }
    for (int i = 3; i &lt; (pow(n,0.5)+1); ++i)
    {
        if(n%i == 0){
            ans = false;
            break;
        }
    }
    return ans;
}
int main(){
    int cases;
    cin&gt;&gt; cases;
    for(int i = 0;i&lt;cases;i++){
        int a, b , ans = 0;
        cin&gt;&gt; a,b;
        for (int j = a; j &lt;= b; ++j)
        {
            if(isPrime(j)){
                ans ++;
            }
        }
        double d = ans/(r-l+1);
        cout&lt;&lt;d;
    }

}


Constraints:

1 ≤ Cases ≤ 100000

1 ≤ A≤ B ≤ 1000000 

How can I optimize it further?

What I researched -

I should check if a i divides n only up till Math.sqrt(n)+1. Also I should do i = i+2 as I have checked for even numbers before only. I should also break the loop once ans becomes false so as to stop any further unnecessary iterations.

for(int i = 3; i&lt;(Math.sqrt(n)+1);i=i+2){
        if(n%i == 0){
            ans = false;
            break;
        }
    }


Here is the link to the question: codechef.
Your question contains 2 pieces of code which makes it hard to review.

Issue specific to the C++ code

Your are using ++i in your code despite having handled the even numbers explicitely before. It should be i+=2 like in your Java code.

Issue in both implementations

Instead of maintaining an ans boolean value, you can simply return false whenever you know that the number can't be prime.

You write your loop like this for(int i = 3; i&lt;(Math.sqrt(n)+1);i=i+2) which is likely to compute the square root at each iteration. The compiler may be able to optimize this out but just in case, it is probably better to store it in a variable beforehand.

Different algorithm

To know whether many numbers are primes, a convenient and efficient algorithm is to use The Sieve of Eratosthenes to build a table to check primes.

You could build it one and for all to get the primes up to the maximum r value.

Going further, you could also build (once) a table giving for each number n the number of primes numbers smaller or equal to n. Then, for each input (a, b), the frequency is something along the lines of ( primes_up_to(b) - primes_up_to(a) / (b - a).