Counting primes in given interval

Question

So, here is a Hackerearth question, regarding (more or less) counting the number of primes between a given pair of numbers (up to 10⁶).

Then there were 3 major options available to me:

1. Trial division method, and its variants.
2. Sieve of Eratosthenes
3. Segmented sieve of Eratosthenes.

As learned from this answer.

The naive method trial division, and its variants gave "Time Limit Exceeded" errors for about 70 % test cases.

Both the Sieve of Eratosthenes and its segmented version gave "Time Limit Exceeded" error for 60 % of the test cases.

Here is my code :

import java.util.* ;
import java.io.BufferedReader ;
import java.io.InputStreamReader ;
/*
Trial division : failed. 6 points
Sieve of Eratosthenes : failed 8 points.
Segmented sieve of Eratosthenes : failed.  8 points.
*/
public class MoguLovesNumbers
{
    public static void main(String args[]) throws Exception
    {
        BufferedReader bro = new BufferedReader(new InputStreamReader(System.in)) ;
        int T = Integer.parseInt(bro.readLine()) ;
        for(int t=0;t<T;t++)
        {
            String[] S = bro.readLine().split(" ") ;
            int l = Integer.parseInt(S[0]) ;
            int r = Integer.parseInt(S[1]) ;
            int temp = l<r?l:r ;
            r = l<r?r:l ;
            l = temp ;


            System.out.println(segmentedSieve(l,r)) ;
        }


    }
    static void sieveOfEratosthenes(int l,int r,List<Integer> prime)
    {
        boolean[] mark = new boolean[r+1] ;
        int counter = 0 ;
        Arrays.fill(mark,true ) ;

        for(int i=2;i<r+1;i++)
        {
            if(mark[i])
            {
                if(i>=l)
                {
                    prime.add(i) ;
                    counter++ ;
                }
                for(int j=i*2;i*i<=r && j<r+1;j+=i)
                    mark[j] = false ;
            }
        }
        // return counter ;
    }
    static int segmentedSieve(int l,int n)
    {
        int limit = (int)Math.sqrt(n)+1 ;
        List<Integer> prime = new ArrayList<Integer>() ;
        sieveOfEratosthenes(0,limit,prime) ;
        int low = limit ;
        int high = limit*2 ;
        int count = 0 ;
        while(low<n)
        {
            if(high>n)
                high = n ;
            boolean mark[] = new boolean[limit+1] ;
            Arrays.fill(mark,true ) ;
            for(int i=0;i<prime.size();i++)
            {
                int loLim = (int)(Math.ceil((float)low/prime.get(i)))*prime.get(i) ;
                for(int j=loLim;j<=high;j+=prime.get(i))
                {
                    mark[j-low] = false ;
                }
            }
            for(int i = 0;i<mark.length;i++)
                if(mark[i] && (i+low>=l)&& (i+low<=high))
                {
                    count++ ;
                }
            low+=limit ;
            high+=limit ;
        }
        if(l<=Math.sqrt(n)+1)
        {
            for(int i=0;i<prime.size();i++)
                if(prime.get(i)>=l)
                    count++ ;
        }
        return count ;

    }
}

SUBMISSIONS:

• Segmented Sieve
• Simple Sieve
• Naive trial division

---

Question:

How can this code be made more efficient? The Segmented Sieve and Simple Sieve both run in O(N log(log(N))) time.

Answer 1

Rethinking it

The obvious change that leaps out at me immediately is to make your list of primes into an object or even class field. Then you don't need to recreate your primes each time. You'd create it the first time. Later you'd just extend it. An object field would be better programming practice, but a class field would work for this problem.

You might even read in all the input first and then create the primes list once for all of them. Or just build it to a million before processing the input. Of course, that would fail if they have some tests where passing means not calculating all million. Given your current algorithm, it would be easy enough to calculate all the primes from 0 to 1000 beforehand.

Consider holding the primes in a NavigableSet. Because what you want to know is how many primes are in a range. So you could replace

            System.out.println(segmentedSieve(l,r)) ;

with

            System.out.println(primes.subSet(l, r).size());

That counts the primes in the set [l, r) if primes is a NavigableSet holding at least all primes less than r.

If you need to count [l, r] or (l, r), you would use the longer version with booleans for inclusiveness.

Specific advice

    static void sieveOfEratosthenes(int l,int r,List<Integer> prime)

You never call this with l as anything but 0. So you might as well say

    static void sieveOfEratosthenes(int r, List<Integer> prime)

Then you can get rid of the check in the loop:

                if(i>=l)

That's always true if l is zero and i is at least 2. You don't have to check it.

You don't need the counter variable. As is, it's equal to prime.size() and you never use it. Eliminating it saves an operation. The compiler might do that for you, but you don't need it.

                for(int j=i*2;i*i<=r && j<r+1;j+=i)

This could be

                for (int j = i*i; j <= r; j += i)

You only need to check from i*i. Anything smaller than that would already be marked. For example, you already marked everything divisible by 2, so i*2 would be marked for all i greater than or equal to 1.

You only needed to check i*i<=r once. This still does that check, as the first iteration j equals i*i.

The j<r+1 and j <= r are equivalent if j and r are integers.