java - 优化 sieve 的代码

Question

这是我编写的用于在上限可以大到 1000000000 的范围之间查找素数的代码。我使用了 Hashmap，除了 2 之外没有存储任何偶数，也没有存储 sero 和 1但当我使用输入 lb = 1 和 ub =1000000000 运行此代码时，它仍然给出运行时错误(内存不足)。请帮忙

这是我的代码:-

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();
     }    
}

收到答案后，我编码了:但它仍然给出 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

将您的算法转换为使用 BitSet相反，您将看到性能和内存使用量的巨大改进。

如果您四处搜索，您会发现该算法的许多变体。例如，您可以看一下:http://www.dreamincode.net/forums/topic/192554-secret-code-vii-prime-numbers/