エラトステネスのシーブの効率を向上させるコード

Question

私はSieve of EratosthenesのコードをJavaで編集しましたが、時間と空間の効率の面で問題があります。

import java.util.*; 

class EratosthenesSeive 
{ 

    public static void main(String args[]) 
    { 

     ArrayList<Long> myPrimeList = new ArrayList<Long>(); 
     ArrayList<Long> myTempPrimeList = new ArrayList<Long>(); 
     ArrayList<Boolean> isPrimeNumber = new ArrayList<Boolean>(); 
     int index = 0; 

     long ul = 1500l; 
     long ll = 2; 

     do 
     { 
      myTempPrimeList.add(ll); 
      isPrimeNumber.add(true); 
      ll++; 
     }while(ll != (ul+1)); 

     for(long i : myTempPrimeList) 
     { 
      if(isPrimeNumber.get(index)) 
      { 
       myPrimeList.add(i); 
       for(long j = i ; j*i <= ul; j++) 
       { 
        isPrimeNumber.set(myTempPrimeList.indexOf(j*i),false); 
       } 
      } 
      index++; 
     } 

     System.out.println(myPrimeList); 
    } 
} 

それはそれは単にハング10^4で、10^5で、私はOutOfMemoryErrorを得る上で、10^3点で最大入力のために正常に動作しているようだ： は、ここでは、コードです。 コードは正常に動作しているようですが、もう少し詳しく説明します。助言がありますか？

Answer 1

可能な最適化の1つは、必要な配列のサイズを事前に知っているので、ArrayListsをプリミティブ型の配列で置き換えることです。これはあなたのコードに現在存在する値の不必要なボクシング/アンボクシングをすべて防ぐのに効果があります。

また、配列に偶数を格納する必要はなく、奇数だけを格納する必要があることに注意してください。メモリ要件およびの処理時間が半減します。

OutOfMemoryErrorを解決するには、起動時にJVMの設定パラメータを操作してアプリケーションのヒープスペースを増やすことができます。

Answer 2

あなたはトンのコードでボクシング/アンボックスしています。 ArrayList<>をプリミティブ型の直線配列に置き換えてみてください。

Answer 3

偶数で作業しないことで速度を倍増させます。

Answer 4

あなたのコードは、必要以上に多くの作業をしています。単一の配列のブール値、非素数をマークする2つのループ、素数のインデックス番号を出力する別のループが必要です。このように：それはさらに多くのヒープ領域が利用できるようにする方法について私を示唆しているため

public void printPrimes(int max) { 

    // declare a single array of booleans 
    boolean[] primeFlags = new boolean[max + 1]; 

    // double loop sieve-style and mark non-primes as true 
    for (int m = 2; m <= (int)Math.sqrt(max); m++) 
     for (int k = m*m; k <= max; k += m) primeFlags[k] = true; 

    // loop over bool array and print indexes with false values 
    // which will be the prime numbers 
    for (int m = 2; m <= max; m++) 
     if (!primeFlags[m]) System.out.print(m + " "); 
} 

Answer 5

import java.util.Scanner; 

//Sieve Of Erastothenes 

public class SieveOfErastothenes { 

    public static void main(String[] args) { 
     Scanner sc = new Scanner(System.in); 
     System.out.print("Enter a range n : "); 
     int n = sc.nextInt(); 

     boolean ar[] = new boolean[n+1]; 
     for (int i=2;i<=n;i++) 
     ar[i] = true; 

     for(int i = 2;i*i<=n;i++) 
     { 
      if(ar[i]) 
      { 
       for(int j=i;i*j<=n;j++) 
        ar[i*j]=false; 
      } 
     } 

     for(int i=2;i<=n;i++) 
     { 
      if(ar[i]) 
       System.out.print(i+" "); 
     } 
     sc.close(); 

    } 

} 

/*This code is contributed by Asish Samantaray*/