球在線判斷素髮電機

Question

我想開發一個可接受的解決方案，以Sphere Online Judge Prime Generator problem。我已經研究了很長時間，並且運氣不錯......我嘗試了各種方法（分解因子，Eratosthenes的篩子，Eratosthenes的分割篩子等等），但是仍然繼續跑向「時間限制超過「錯誤。我的代碼如下，我歡迎任何和所有的建議和意見。提前致謝！

作爲一個說明，我也發佈在Code Review這個。我得到的一個迴應主要集中在一般編碼最佳實踐上，我當然讚賞並考慮到了這些。但是，我目前的主要目標是編寫一個Sphere接受的解決方案，並遵循其中的最佳實踐。

package info.danforbes.sphere; 

import java.io.BufferedReader; 
import java.io.BufferedWriter; 
import java.io.FileReader; 
import java.io.FileWriter; 
import java.io.IOException; 
import java.io.InputStreamReader; 
import java.io.OutputStreamWriter; 
import java.util.ArrayList; 
import java.util.BitSet; 
import java.util.List; 

/** 
* Generate all prime numbers between two given numbers. 
* The input begins with the number t of test cases on a single line (t <= 10). 
* In each of the next t lines there are two numbers m and n (1 <= m <= n <= 1000000000, n - m <= 100000) separated by a space. 
* For every test case print all prime numbers p such that m <= p <= n, one number per line, test cases separated by an empty line. 
*/ 
public class Problem02 { 
    // the upper limit on the number of primes to pre-compute 
    private static final int SIEVE_LIMIT = (int)Math.floor(Math.sqrt(1000000000)) + 1; 
    // pre-computed composites 
    private static final BitSet COMPOSITES = new BitSet(SIEVE_LIMIT); 
    // pre-computed primes 
    private static final List<Integer> PRIMES = new ArrayList<Integer>(); 

    /** 
    * Read in input and generate output 
    * @param args optional list of I/O file names (used for testing) 
    */ 
    public static void main(String[] args) { 
    // variable declarations 
    BufferedReader inStream = null; 
    BufferedWriter outStream = null; 
    int outerSieveNdx, innerSieveNdx, numCases, spaceNdx, beg, end; 
    String line; 
    StringBuilder resultBuilder = new StringBuilder(); 

    //pre-compute a set using Sieve of Eratosthenes method 
    COMPOSITES.set(0); 
    COMPOSITES.set(1); 

    for (outerSieveNdx = 2; outerSieveNdx * outerSieveNdx < SIEVE_LIMIT; ++outerSieveNdx) { 
     for (innerSieveNdx = outerSieveNdx * outerSieveNdx; innerSieveNdx < SIEVE_LIMIT; innerSieveNdx += outerSieveNdx) { 
     COMPOSITES.set(innerSieveNdx); 
     } 
    } 

    for (outerSieveNdx = 2; outerSieveNdx < SIEVE_LIMIT; outerSieveNdx = COMPOSITES.nextClearBit(outerSieveNdx + 1)) { 
     PRIMES.add(outerSieveNdx); 
    } 

    // set input and output streams if file names are not provided 
    if (args.length == 0) { 
     inStream = new BufferedReader(new InputStreamReader(System.in)); 
     outStream = new BufferedWriter(new OutputStreamWriter(System.out)); 
    } 

    try { 
     // set input and output stream if file names were provided (testing purposes) 
     if (inStream == null && outStream == null) { 
     inStream = new BufferedReader(new FileReader(args[0])); 
     outStream = new BufferedWriter(new FileWriter(args[1])); 
     } 

     // get the number of cases in this run 
     numCases = Integer.parseInt(inStream.readLine()); 

     BitSet segmentedSieve = null; 
     // get the ranges for each case & generate the primes for each range 
     for (outerSieveNdx = 0; outerSieveNdx < numCases; ++outerSieveNdx) { 
     line = inStream.readLine(); 
     spaceNdx = line.indexOf(' '); 
     beg = Integer.parseInt(line.substring(0, spaceNdx)); 
     end = Integer.parseInt(line.substring(spaceNdx + 1)); 

     // get segmented sieve for this range and add primes to result 
     segmentedSieve = segmentedSieve(beg, end); 
     for (int ndx = segmentedSieve.nextClearBit(0); ndx <= end - beg; ndx = segmentedSieve.nextClearBit(ndx + 1)) { 
      resultBuilder.append(Integer.toString(beg + ndx) + '\n'); 
     } 

     resultBuilder.append('\n'); 
     } 

     // clean up, output result and exit 
     inStream.close(); 
     outStream.write(resultBuilder.toString().trim()); 
     outStream.close(); 
     return; 
    } catch (IOException e) { 
     e.printStackTrace(); 
    } 
    } 

    /** 
    * Execute a segmented Sieve of Eratosthenes. 
    * @param beg the first number in the segment 
    * @param end the last number in the segment 
    * @return a BitSet with indices corresponding to composite numbers set TRUE 
    */ 
    public static BitSet segmentedSieve(int beg, int end) { 
    BitSet segmentedSieve = null; 

    if (end < SIEVE_LIMIT) { 
     segmentedSieve = COMPOSITES; 
    } else { 
     final int SET_SIZE = end - beg; 
     int innerSieveNdx; 

     segmentedSieve = new BitSet(SET_SIZE); 
     for (int outerSieveNdx = COMPOSITES.nextClearBit(0); outerSieveNdx < SIEVE_LIMIT; outerSieveNdx = COMPOSITES.nextClearBit(outerSieveNdx + 1)) { 
     innerSieveNdx = beg; 

     while (innerSieveNdx % outerSieveNdx != 0) { 
      ++innerSieveNdx; 
     } 

     for (; innerSieveNdx <= end; innerSieveNdx += outerSieveNdx) { 
      segmentedSieve.set(innerSieveNdx - beg); 
     } 
     } 
    } 

    return segmentedSieve; 
    } 
} 

Answer 1

我回答了這個問題關閉它，但信用真的去@DanielFischer。我認爲最大的影響因素是BitSet數據結構的緩慢。 Sphere接受的代碼如下。如果有人有任何進一步的建議，我很樂意聽到他們。

import java.io.BufferedReader; 
import java.io.BufferedWriter; 
import java.io.InputStreamReader; 
import java.io.OutputStreamWriter; 
import java.util.ArrayList; 

/** 
* Generate all prime numbers between two given numbers. 
* The input begins with the number t of test cases on a single line (t <= 10). 
* In each of the next t lines there are two numbers m and n (1 <= m <= n <= 1000000000, n - m <= 100000) separated by a space. 
* For every test case print all prime numbers p such that m <= p <= n, one number per line, test cases separated by an empty line. 
*/ 
public class Main { 
    // the upper limit on the number of primes to pre-compute 
    private static final int SIEVE_LIMIT = (int)Math.floor(Math.sqrt(1000000000)) + 1; 
    // pre-computed composites 
    private static final boolean[] COMPOSITES = new boolean[SIEVE_LIMIT]; 
// // pre-computed primes 
    private static final ArrayList<Integer> PRIMES = new ArrayList<Integer>(); 

    /** 
    * Read in input and generate output 
    * @param args optional list of I/O file names (used for testing) 
    */ 
    public static void main(String[] args) { 
    // variable declarations 
    BufferedReader inStream = null; 
    BufferedWriter outStream = null; 
    int outerSieveNdx, innerSieveNdx, numCases, spaceNdx, beg, end, limit; 
    String line = null; 
    boolean[] segmentedSieve = null; 
    StringBuilder resultBuilder = new StringBuilder(); 

    //pre-compute a set of primes using Sieve of Eratosthenes method 
    COMPOSITES[0] = true; 
    COMPOSITES[1] = true; 

    for (outerSieveNdx = 2; outerSieveNdx * outerSieveNdx < SIEVE_LIMIT; ++outerSieveNdx) { 
     for (innerSieveNdx = outerSieveNdx * outerSieveNdx; innerSieveNdx < SIEVE_LIMIT; innerSieveNdx += outerSieveNdx) { 
     COMPOSITES[innerSieveNdx] = true; 
     } 
    } 

    for (outerSieveNdx = 2; outerSieveNdx < SIEVE_LIMIT; ++outerSieveNdx) { 
     if (!COMPOSITES[outerSieveNdx]) PRIMES.add(outerSieveNdx); 
    } 

    // set input and output streams if file names are not provided 
    inStream = new BufferedReader(new InputStreamReader(System.in)); 
    outStream = new BufferedWriter(new OutputStreamWriter(System.out)); 

    try { 
     // get the number of cases in this run 
     numCases = Integer.parseInt(inStream.readLine()); 

     // get the ranges for each case & generate the primes for each range 
     for (outerSieveNdx = 0; outerSieveNdx < numCases; ++outerSieveNdx) { 
     line = inStream.readLine(); 
     spaceNdx = line.indexOf(' '); 
     beg = Integer.parseInt(line.substring(0, spaceNdx)); 
     end = Integer.parseInt(line.substring(spaceNdx + 1)); 

     // if the end is smaller than the largest pre-computed prime, just use the pre-computed list 
     if (end < SIEVE_LIMIT) { 
      for (int aPrime : PRIMES) { 
      if (aPrime > end) break; 
      else { 
       if (aPrime >= beg) { 
       resultBuilder.append(Integer.toString(aPrime) + '\n'); 
       } 
      } 
      } 
     // if the beginning is larger than the largest pre-computed prime, use a segmented sieve 
     } else if (beg > SIEVE_LIMIT) { 
      segmentedSieve = segmentedSieve(beg, end); 
      for (innerSieveNdx = 0; innerSieveNdx < segmentedSieve.length; ++innerSieveNdx) { 
      if (!segmentedSieve[innerSieveNdx]) { 
       resultBuilder.append(Integer.toString(beg + innerSieveNdx) + '\n'); 
      } 
      } 
     // if both of the above are false, use a combined method 
     } else { 
      for (int aPrime : PRIMES) { 
      if (aPrime >= beg) { 
       resultBuilder.append(Integer.toString(aPrime) + '\n'); 
      } 
      } 

      segmentedSieve = segmentedSieve(SIEVE_LIMIT, end); 

      limit = end - SIEVE_LIMIT; 
      for (innerSieveNdx = 0; innerSieveNdx <= limit; ++innerSieveNdx) { 
      if (!segmentedSieve[innerSieveNdx]) { 
       resultBuilder.append(Integer.toString(SIEVE_LIMIT + innerSieveNdx) + '\n'); 
      } 
      } 
     } 

     resultBuilder.append('\n'); 
     } 

     // clean up, output result and exit 
     inStream.close(); 
     outStream.write(resultBuilder.toString().trim()); 
     outStream.close(); 
     return; 
    } catch (Exception e) { 
     e.printStackTrace(); 
    } 
    } 

    /** 
    * Execute a segmented Sieve of Eratosthenes. 
    * @param beg the first number in the segment 
    * @param end the last number in the segment 
    * @return a BitSet with indices corresponding to composite numbers set TRUE 
    */ 
    public static boolean[] segmentedSieve(int beg, int end) { 
    boolean[] segmentedSieve = null; 

    int innerSieveNdx; 
    int limit = (int)Math.ceil(Math.sqrt(end)); 
    int remainder; 

    segmentedSieve = new boolean[end - beg + 1]; 
    for (int aPrime : PRIMES) { 
     if (aPrime > limit) break; 
     innerSieveNdx = beg; 

     remainder = innerSieveNdx % aPrime; 
     if (remainder != 0) { 
     innerSieveNdx += aPrime - remainder; 
     } 

     for (; innerSieveNdx <= end; innerSieveNdx += aPrime) { 
     segmentedSieve[innerSieveNdx - beg] = true; 
     } 
    } 

    return segmentedSieve; 
    } 
} 

Answer 2

沒有使用篩網，只是微不足道的方法。

import java.util.*; 
import java.lang.*; 
import java.lang.Math; 

public class Main{ 
public static void main (String[] args) throws java.lang.Exception{ 
    Scanner sc = new Scanner(System.in); 
    int testCases = sc.nextInt(); 
    int ranges[][] = new int[testCases][2]; 
    for(int i=0 ; i<testCases ; i++){ 
     ranges[i][0] = sc.nextInt(); 
     ranges[i][1] = sc.nextInt(); 
    } 

    for(int i=0 ; i<testCases ; i++){ 
     int m = ranges[i][0]; 
     int n = ranges[i][1]; 
     double sqrt = 0.0; 
     //generatePrime(m,n); 
     int j=0; 
     for(int k=m ; k<=n ; k++){ 
      if(k==1) continue; 
      if(k==2) {System.out.println(k); continue;} 
      //if(k==3) {System.out.println(k); continue;} 
      if(k%2 != 0){ 
       sqrt = Math.sqrt(k); 
       for(j=3 ; j<=sqrt ; j=j+2){ 
        if(k%j==0) break; 
       } 

       if(j>sqrt) 
        System.out.println(k); 
      } 


     } 

     if(i<testCases-1) 
     System.out.println(); 
    } 

    sc.close(); 
} 
}