Effecient Use Sieve of Eratosthenes algorithm

Question

Given this as a the Problem Statement

Given two numbers, find the sum of prime numbers between them, both inclusive.

Input:

The first line contains the number of test cases T. Each test case contains two space separated integers.

Output:

Print the answer on a new line for each case.

Constraints:

1 <= T <= 100

1 <= a,b < 10^6

. Here is the working code of mine, that has been accepted.

class TestClass {
 public static void main(String args[] ) throws Exception {
 BufferedReader keyboard= new BufferedReader(new InputStreamReader(System.in));
 int t=Integer.parseInt(keyboard.readLine());
 while(t>0 && t<=100){
 String[] tempInt=keyboard.readLine().split(" ");
 int n=Integer.parseInt(tempInt[0]);
 int m=Integer.parseInt(tempInt[1]);
 int sum=primeSum(n,m);
 System.out.println(sum);
 t--;
 }
 }
private static int primeSum(int n, int m) {
 int sum=0;
 int maxFactor= (int)Math.sqrt(m);
 boolean[] isPrime=new boolean[m + 1];
 int len=isPrime.length;
 Arrays.fill(isPrime,true);
 isPrime[0]=false;
 isPrime[1]=false;
 for(int i=0;i<=maxFactor;i++){
 if(isPrime[i]){
 for(int j=i+i;j<len;j+=i){
 isPrime[j]=false;
 }
 }
 }
 for(int i=n;i<=m;i++){
 if(isPrime[i]){
 sum=sum+i;
 }
 }
 return sum;
 }
}

But what is really bugging me is this line boolean[] isPrime=new boolean[m + 1];. Where i Have to use really large block of space. How could i avoid such large allocation while being effiecient too.? What are futher way of improvement of this code apart from array allocation ?

• kraskevich: I would not say that an array of 1 million booleans is really that large. A BitSet may save some memory(it does not change asymptotic behavior, though).

Answer 1

Ways to decrease the allocation

Since your main question was about the allocation length, I'll suggest two ways to decrease the allocation (although 1 MB really isn't that much to begin with).

1. Since the only even number that is prime is 2, you can only allocate half the amount by only considering odd numbers. When you perform the sieve, you skip all even numbers and use index [j/2] for each odd number. Just remember at the end to count 2 as one of the primes if the range includes it.

2. You can use 1 bit per number instead of 1 boolean per number. You can use BitSet or your own bit array.

Combining both of the above allows you to allocate 1/16 the amount that you originally allocated (so about 64KB instead of 1MB). I don't think it will help at all though. If anything, your program will only get slower.

Reuse the allocation

Also, since you are running up to 100 test cases, you might as well just run the sieve once on the maximum input (10^6). Then you can compute the 100 answers quickly without redoing all the work each time.

• Ankur Anand: while all the point i understood .. but about reuse of the allocation it was great help buddy .. Point noted for future too :)

Answer 2

1. An array of 1 million booleans is not that large(1 boolean takes one 1 byte, so it occupies about 1 MB of memory). Using a BitSet may save some memory, but it is not necessary under given constraints.

2. I'd recommend formatting the code properly to improve readability. It is conventional to surround binary operators with whitespaces. Take a look at this piece of code:

   for (int i = 0; i <= maxFactor; i++) {
    if (isPrime[i]) {
    for(int j = i + i; j < len; j += i){
    isPrime[j] = false;
    }
    }
   }
   

   It is more readable than:

   for(int i=0;i<=maxFactor;i++){
    if(isPrime[i]){
    for(int j=i+i;j<len;j+=i){
    isPrime[j]=false;
    }
    }
   }
   

   ,isn't it?

3. A while loop in the main method looks strange. When the number of iterations is known beforehand, using a for loop makes your intentions more clear.

• Ankur Anand: All the point noted .. especially second and third :)