optimizing the code for sieve

Question

Here is the code that i have written for finding prime numbers between a range where the upper bound can be as big as 1000000000.I have used Hashmap and have not stored any even number except 2 and havent stored sero and one as well.But still when I run this code with input lb = 1 and ub =1000000000,it gives runtime error,(out of memory).Please help

Here is my code :-

import java.util.HashMap;
import java.util.Iterator;

import java.util.Scanner;

class Samp {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int t, limit, m, n;
        double lb, ub, c;

        t = sc.nextInt();
        while (t > 0) {
            c = 3;
        HashMap<Integer, Boolean> primeflags = new HashMap<Integer, Boolean>();
            primeflags.put(2, true);
            lb = sc.nextDouble();
            ub = sc.nextDouble();
            while (c <= ub) {
                primeflags.put((int) c, true);
                c = c + 2;
            }
            limit = (int) Math.sqrt(ub);

            for (m = 2; m <= limit; m++) {

                for (n = m * m; n <= ub; n += m) {

                    if (primeflags.containsKey(n))
                        primeflags.remove(n);
                }

            }
            Iterator<Integer> iterator = primeflags.keySet().iterator();
            while (iterator.hasNext()) {  
                   Integer key = (Integer) iterator.next(); 

                   if(key >= lb)
                   System.out.println(key); 
                }



            --t;

        }
       sc.close();
     }    
}

ok after recieving the answers ,I coded this : But still it is giving TLE

import java.util.BitSet;
import java.util.Scanner;
public class Prime {
    private static BitSet bitSet = new BitSet(1000);
    private static int max = 3;

      public static boolean isPrime(int n) {
          if(n == 2)
                      return true;
          if(n < 3 || n % 2 == 0)
               return false;
          if(n <= max)
              return !bitSet.get(n / 2);
          for(int i = 3; i <= n; i += 2) {
              if(i * 2 > n)
                 break;
              if(!bitSet.get(i / 2)) {
                  int multiple = max / i;
                  multiple *= i;
                  if(multiple <= i)
                multiple = i * 2;
                  clearMultiple(i, multiple, n);  
              }
          }
          max = n;
          return !bitSet.get(n / 2);
      }

    private static void clearMultiple(int prime, int multiple, int max) {
        while(multiple <= max) {
                    setNotPrime(multiple);
                    multiple += prime;
                   }

    }

    private static  void setNotPrime(int n) {

        if(n % 2 == 0)
             return;
              bitSet.set(n / 2, true);
}     


    public static void getPrimeGreaterOrEqual(int n,int upperbound) {
            // make sure we start with an odd number
        if( n == 1 || n == 0){
            System.out.println(2);
            n = 3;
        }    
    if(n % 2 == 0 && n != 2)
                    ++n;
                // loop until we found one
                    while(n <= upperbound) {
                //if the number is registered as prime return it
                if(isPrime(n))
                       System.out.println(n);
                       // else check next one
                        n += 2;


               }  
            }

    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        int t,lb,ub;
         t = sc.nextInt();
        while(t > 0){
            lb = sc.nextInt();
            ub = sc.nextInt();

            getPrimeGreaterOrEqual(lb, ub);

            --t;
       }
       sc.close();
    }
}

Answer 1

I have no implementation for Java at hand. I have written the following implementation in C++ and used it to calculate prime numbers up to 1.000.000.000.000:

void sieve(std::size_t bound, std::ostream& os)
{
    using uint_t = unsigned int;
    constexpr auto bits = sizeof(uint_t) * CHAR_BIT;
    auto&& index = [](std::size_t i) { return (i - 3) / 2 / bits; };
    auto&& mask = [](std::size_t i) { return uint_t{1} << ((i - 3) / 2 % bits); };
    auto size = index(bound - 1) + 1;
    std::unique_ptr<uint_t[]> crossed{new uint_t[size]};
    std::fill(crossed.get(), crossed.get() + size, uint_t{0});
    for (std::size_t i = 3; i < bound; i += 2) {
        if ((crossed[index(i)] & mask(i)) == 0) {
            auto q = i * i;
            if (q >= bound) {
                break;
            }
            for (; q < bound; q += i) {
                crossed[index(q)] |= mask(q);
            }
        }
    }
    os << "2\n";
    for (std::size_t i = 3; i < bound; i += 2) {
        if ((crossed[index(i)] & mask(i)) == 0) {
            os << i << '\n';
        }
    }
}

Answer 2

You can put primenumber after find. So you dont need more memory. And you can run your code with this option. -Xms512M -Xmx2048M

Answer 3

Convert your algorithm to use a BitSet instead, and you will see huge performance and memory usage improvements.

You'll find many variants of this algorithm if you search around. You could for instance take a look at this: http://www.dreamincode.net/forums/topic/192554-secret-code-vii-prime-numbers/