Segmented Sieve to find primes in a range

There are many approaches to find the primes below a specific number. few better approaches will be Sieve of Eratosthenes and Segmented Sieve (for larger limit).

Below are the Java implementation of both.

Sieve of Eratosthenes Java Implementation

/**
  * @param limit : The limit can not be large as 1000,000,000
  * @return List of primes up to limit, i.e. in the range [0, limit]
  */
    static List< integer > simpleSieve(int limit) {
         boolean mark[] = new boolean[limit];
         Arrays.fill(mark, true);

         for (int p = 2; p * p < limit; p++) {
              // If p is not changed, then it is a prime
              if (mark[p] == true) {
                  // Update all multiples of p
                  for (int i = p * 2; i < limit; i += p) {
                      mark[i] = false;
                  }
              }
         }

         List< integer > list = new ArrayList<>();
         for (int i = 2; i < limit; i++) {
             if (mark[i]) {
                 list.add(i);
                 count++;
             }
         }
         return list;
    }

Segmented Sieve Java Implementation

/**
  * @param n : The value n can be large
  * @return List of primes up to n, i.e. in the range [0, n]
  */
    static List< integer > segmentedSieve(int n) {
        int limit = (int) Math.sqrt(n) + 1;
        List< integer > primes = simpleSieve(limit);
        List< integer > primesFinalList = new ArrayList<>();
        primesFinalList.addAll(primes);
        int low = 2;
        int high = limit;

        while (low < n) {
            boolean mark[] = new boolean[limit + 1];
            Arrays.fill(mark, true);

            for (int i = 0; i < primes.size(); i++) {
                int temp = primes.get(i);
                int loLim = (int) Math.floor(low * 1.0 / temp) * temp;
                if (loLim < low) {
                    loLim += temp;
                }
                for (int j = loLim; j < high; j += temp) {
                    mark[j - low] = false;
                }
            }
            for (int i = low; i < high; i++) {
                if (mark[i - low] == true) {
                    primesFinalList.add(i);
                    count++;
                }
            }
            low = low + limit;
            high = high + limit;
            if (high >= n) {
                high = n;
            }
         }
         return primesFinalList;
    }

Segmented Sieve for a Range

/**
  * @param leftLimit
  * @param rightLimit
  * @param maxRangeCapacity
  *            : maximum value for (rightLimit - leftLimit)
  * @return primes in the range [leftLimit, rightLimit]
  */
    static List< Integer > segmentedSieveForRange(int leftLimit, int rightLimit,
       int maxRangeCapacity) {
        List< Integer > list = new ArrayList<>();
        // max limit to consider is 1000,000,000
        // sqrt(1000,000,000) <= 31623 ; so lets find all primes upto 40,000
        // with a
        // safe margin
        boolean[] shieves = new boolean[40000];
        int numberOfPrimes = 0;
        // the number of primes below 40,000 is less than 4205 (can even find
        // from brute force)
        int[] index = new int[4205];
        // mark all as true (i.e. as primes)
        Arrays.fill(shieves, true);

        for (int i = 2; i * i < shieves.length - 1; i++) {
            if (shieves[i]) {
                // Update all multiples of i. NOTE : i is a prime
                for (int j = i; i * j < shieves.length; j++) {
                    shieves[j * i] = false;
                }
            }
        }

        // fill the index array where we store our primes below 40000
        for (int i = 0; i < shieves.length; i++) {
            if (shieves[i]) {
                index[numberOfPrimes++] = i;
            }
        }

        if (leftLimit < 2) {
            // the smallest prime
            leftLimit = 2;
        }
        // maxRangeCapacity = 1000,000
        boolean[] isPrime = new boolean[maxRangeCapacity + 1];
        Arrays.fill(isPrime, true);

        for (int k = 2; k < numberOfPrimes; k++) {
            int u = index[k];
            int start = 0;
   
            if (u >= leftLimit) {
                start = 2 * u;
            } else {
                start = leftLimit + ((u - leftLimit % u) % u);
            }

            for (int l = start; l <= rightLimit; l += u) {
                isPrime[l - leftLimit] = false;
            }
        }
  
        for (int p = leftLimit; p <= rightLimit; p++) {
            if (isPrime[p - leftLimit]) {
                list.add(p);
            }
        }
  
        return list;
    }

Sample solution to the problem Twins in Hackerrank

public class TwinPrime {

    public static void main(String[] args) throws NumberFormatException,
      IOException {

         BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
         BufferedWriter out = new BufferedWriter(new OutputStreamWriter(
         System.out));

         String[] temp = in.readLine().split(" ");
         int x = Integer.parseInt(temp[0]);
         int y = Integer.parseInt(temp[1]);

         List< Integer > list = segmentedSieveForRange(x, y, 1000000);

         int count = 0;
         int size = list.size();
         for (int i = 0; i < size - 1; i++) {
             if (list.get(i + 1) - list.get(i) == 2) {
                 count++;
             }
         }
         System.out.println(count);
 }

 /**
  * @param leftLimit
  * @param rightLimit
  * @param maxRangeCapacity
  *            : maximum value for (rightLimit - leftLimit)
  * @return primes in the range [leftLimit, rightLimit]
  */
    static List< Integer > segmentedSieveForRange(int leftLimit, int rightLimit,
      int maxRangeCapacity) {
         List< Integer > list = new ArrayList<>();
         // max limit to consider is 1000,000,000
         // sqrt(1000,000,000) <= 31623 ; so lets find all primes upto 40,000
         // with a
         // safe margin
         boolean[] shieves = new boolean[40000];
         int numberOfPrimes = 0;
         // the number of primes below 40,000 is less than 4205 (can even find
         // from brute force)
         int[] index = new int[4205];
         // mark all as true (i.e. as primes)
         Arrays.fill(shieves, true);

         for (int i = 2; i * i < shieves.length - 1; i++) {
             if (shieves[i]) {
                 // Update all multiples of i. NOTE : i is a prime
                 for (int j = i; i * j < shieves.length; j++) {
                     shieves[j * i] = false;
                 }
             }
         }

         // fill the index array where we store our primes below 40000
         for (int i = 0; i < shieves.length; i++) {
             if (shieves[i]) {
                 index[numberOfPrimes++] = i;
             }
         }

         if (leftLimit < 2) {
             // the smallest prime
             leftLimit = 2;
         }
         // maxRangeCapacity = 1000,000
         boolean[] isPrime = new boolean[maxRangeCapacity + 1];
         Arrays.fill(isPrime, true);

         for (int k = 2; k < numberOfPrimes; k++) {
             int u = index[k];
             int start = 0;
   
             if (u >= leftLimit) {
                 start = 2 * u;
             } else {
                 start = leftLimit + ((u - leftLimit % u) % u);
             }

             for (int l = start; l <= rightLimit; l += u) {
                 isPrime[l - leftLimit] = false;
             }
         }
  
         for (int p = leftLimit; p <= rightLimit; p++) {
             if (isPrime[p - leftLimit]) {
                 list.add(p);
             }
         }
  
         return list;
    }

}

Posted in: