这是我写的用于在上限可以达到1000000000的范围内查找素数的代码。我使用了Hashmap并没有存储偶数,除了2和没有存储sero还有一个。当我使用输入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();
    }
}

最佳答案

将您的算法转换为使用BitSet,您将看到性能和内存使用方面的巨大改进。

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

09-10 03:55
查看更多