Prime generator for SPOJ

Question

I have written code to solve the prime generator problem. I am given an input which contains in the first line the number of test cases, and for each test case, I am given a range and I have to print the list of prime numbers in that range. However, it doesn't pass and says that time limit has exceeded. I tried optimizing the code as best as I could, but I couldn't find any further optimization.

import java.util.LinkedHashSet;
import java.util.Scanner;
import java.util.Set;


class Primes {

private static Set<Long> primes = new LinkedHashSet<Long>();
private static long biggestPrime = 0;

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int numberOfTC = scanner.nextInt();

    for (int i = 0; i < numberOfTC; i++) {

        long a = scanner.nextInt();
        long b = scanner.nextInt();
        long startFrom = a;

        if (a >= biggestPrime) {
            startFrom = biggestPrime;
        } 
        if (biggestPrime == 0) {
            startFrom = 2;
        }
        for (long j = startFrom; j <= b; j++) {
            if (isPrime(j) && j >=a)  {
                System.out.println(j);
            }
        }
        System.out.println();
    }
    scanner.close();

}

private static boolean isPrime(long x) {
    if (x < biggestPrime) {
        if (primes.contains(x)) {
            return true;
        }
        return false;
    }
    for (Long prime : primes)
    {
        if (prime*prime > x ) {
            break;
        }
        if (x % prime == 0) {
            return false;
        }
    }
    if (biggestPrime < x) {
        primes.add(x);
        biggestPrime = x;
    }
    return true;
}
} 

Answer 1

The essence of the algorithm used by a sieve is removing the factors of the number. eg. first we remove the factors of 2 ie. 4,6, 8,10... , and then factors of 3 ie. 9 12, 15... so on and so forth.

But applying the same logic for bigger constraints would result in TLE. Thus segment sieve comes into picture.

The segment sieve also applies the same logic BUT on the segment. Thus, Segment Sieve works only if the segment length is within manageable constraints.

Consider a segment given by [m,n]. We remove all the factors which are greater than m but less than n. To check whether a number between m and n is a factor, we use a boolean array(is_factor)...whereis_factor[i] denotes whether the number which at a offset of i from lower bound of the segment(m). Now the factors are eliminated by considered all the numbers which are less than the sqrt(n).

Let's consider an example to illustrate my point.

Suppose m=1000 and n=1100 So we will remove all the factors of x( where x ranges from 2 to sqrt(1000)).

Therefore, When x=2---> 1000,1002,1004,....1100 get crossed..(corresponding is_factor gets marked).

When x=3 --> 1002,1005,1008,....1098 get crossed.. And the process continues.

So the ones which remain unmarked are the primes in the interval [m,n]. This link illustrates a C++ program for solving the problem Prime 1 SPOJ . Hope this helps mate :)

Answer 2

public class SPOJ_Prime1 {

    private static final long LARGEST_CANDIDATE = 1000000000;
    private static final int SEGMENT_SIZE  = (int)Math.sqrt(LARGEST_CANDIDATE) + 1;
    private static SortedSet<Long> primes = new TreeSet<>();

    private static void sieve(int n, boolean[] composites) {
        // all multiples of n smaller than n*n will already be marked 
        // from previous sieve operations
        sieve(n, composites, n * n);
    }

    private static void sieve(int n, boolean[] composites, int minimum) {
        for (int i = minimum; i < composites.length; i += n) {
            composites[i] = true;
        }
    }

    private static void generatePrimes() {
        boolean [] composites = new boolean[SEGMENT_SIZE];

        primes.add(2L);
        primes.add(3L);

        // start with an increment of 4 because we update before first use
        int increment = 4;

        for (int i = 5; i < composites.length; i += increment) {
            if (!composites[i]) {
                // if not a multiple of a smaller number,
                // must be prime
                // so mark all multiples of it as composite
                sieve(i, composites);
                primes.add((long) i);
            }

            increment = 6 - increment;
        }
    }

    private static Collection<Long> generatePrimesInSegment(long low, long high) {
        List<Long> results = new ArrayList<>();

        // if high is no larger than the largest prime
        if (high <= primes.last()) {
            // we can just return the low/high subset of the existing primes
            for (long prime : primes.subSet(low, high)) {
                results.add(prime);
            }

            return results;
        }

        // if low is no larger than the largest prime
        if (low <= primes.last()) {
            // put all the primes from low up to the largest prime in the results
            for (long prime : primes.tailSet(low)) {
                results.add(prime);
            }

            // update low so that is larger than the largest prime
            low = primes.last() + 1;
        }

        boolean [] composites = new boolean[(int)(high - low + 1)];
        for (long prime : primes) {
            // we want minimum to range from 0 to prime - 1
            long minimum = low % prime;
            if (minimum != 0) {
                // minimum is how far below low that the last multiple is
                // so change it to be the next multiple after low
                minimum = prime - minimum;
            }

            sieve((int)prime, composites, (int)minimum);
        }

        // add the primes in the segment to the results
        for (int i = 0; i < composites.length; i++) {
            if (!composites[i]) {
                results.add(low + i);
            }
        }

        return results;
    }

    public static void main(String[] args) {
        generatePrimes();

        try (Scanner scanner = new Scanner(System.in)) {
            for (int numberOfTC = scanner.nextInt(); 0 < numberOfTC; numberOfTC--) {
                for (long i : generatePrimesInSegment(scanner.nextLong(), scanner.nextLong())) {
                    System.out.println(i);
                }

                System.out.println();
            }
        }
    }

}

Some points. This version uses a try-with-resources to manage the Scanner. We could easily catch exceptions if we wanted to do so.

I eliminated intermediate variables and just assign the results of input directly. This makes main shorter.

Because a prime number must have at least one factor less than its square root, in order to test for primality, we only need to check divisibility by primes up to the square root of the largest possible candidate (as given in the problem statement). So I first generate those primes. After that, I use a sieve on just the given segments. This is the segmented version of your original sieving algorithm.

When generating the initial primes, I used the normal shortcuts. I added 2 and 3 without checking. I increment by an alternating interval of 2 and 4 such that we skip all multiples of 2 and 3. That saves sieving them out.