2
\$\begingroup\$

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<cases; i++){
            int l = sc.nextInt();
            int r = sc.nextInt();

            double ans = 0.0;
            for(int j = l; j<=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>5&& n%5==0){
            ans = false;
        }
        if(n>2&&n%2 == 0){
            ans = false;
        }
        else{
        for(int i = 3; i<(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 <iostream>
#include <math.h>
using namespace std;
bool isPrime(int n){
    bool ans= true;
    if(n == 1){
        ans = false;
    }
    if(n > 2 && n%2 == 0){
        ans = false;
    }
    for (int i = 3; i < (pow(n,0.5)+1); ++i)
    {
        if(n%i == 0){
            ans = false;
            break;
        }
    }
    return ans;
}
int main(){
    int cases;
    cin>> cases;
    for(int i = 0;i<cases;i++){
        int a, b , ans = 0;
        cin>> a,b;
        for (int j = a; j <= b; ++j)
        {
            if(isPrime(j)){
                ans ++;
            }
        }
        double d = ans/(r-l+1);
        cout<<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<(Math.sqrt(n)+1);i=i+2){
        if(n%i == 0){
            ans = false;
            break;
        }
    }

Here is the link to the question: codechef.

\$\endgroup\$
  • \$\begingroup\$ "How can I optimize it further?" Lookup The sieve of Erasthotenes. \$\endgroup\$ – πάντα ῥεῖ Feb 18 '18 at 12:29
  • \$\begingroup\$ Guys please do not down vote the question just because you don't know it. At least notify me in the comments what the question is lacking \$\endgroup\$ – Arhaan Ahmad Feb 18 '18 at 12:29
  • 4
    \$\begingroup\$ "... what the question is lacking" Research and efforts. \$\endgroup\$ – πάντα ῥεῖ Feb 18 '18 at 12:30
  • \$\begingroup\$ I have a vague recollection of a formula to estimate the number of prime numbers less than a certain number, which relies on the Riemann hypothesis. Are you sure you need to count them one by one? \$\endgroup\$ – papagaga Feb 18 '18 at 13:22
  • 2
    \$\begingroup\$ "please do not down vote the question just because you don't know it" That's a dangerous assumption. Questions get downvoted if they lack quality. If anything, difficult questions tend to attract a lot of upvotes if they're well stated. \$\endgroup\$ – Mast Feb 18 '18 at 14:38
8
\$\begingroup\$

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<(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).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.