在java中提高Eratosthenes代碼的效率

我已經在Java中使用了代碼Sieve of Eratosthenes，但我面臨一些時間和空間效率問題。下面的代碼：在java中提高Eratosthenes代碼的效率

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^3是工作的罰款，在10^4它只是掛在10^5以上，我得到OutOfMemoryError。而代碼似乎工作正常，但我想多扣一點。有什麼建議麼？

來源

2012-02-22 Kazekage Gaara

一個可能的優化將與基本類型數組被替換的ArrayList，因爲你事先知道所需要的數組的大小。這將會阻止你的代碼中當前存在的所有不必要的裝箱/拆箱操作。

另外，請注意，您不必在數組中存儲偶數，只有奇數 - 這樣可以將內存需求減少一半，處理時間減少和。

爲解決OutOfMemoryError異常，你可以在啓動時使用JVM的配置參數不甘示弱，使得提供更多的堆空間的應用程序。

來源

2012-02-22 18:34:45

您在該代碼中裝箱/拆箱噸。您可能想嘗試用原始類型的直接數組替換ArrayList<>。

來源

2012-02-22 18:29:25 dlev

只好選擇對方的回答是正確的之一，因爲它甚至建議我如何使更多的堆空間。 :-) – 2012-02-22 18:46:42

不用擔心 - 這一切都是爲了解決問題！ – dlev 2012-02-22 18:54:11

啊，幾乎不太一般的美... – Blindy 2012-02-22 18:59:07

通過不與偶數一起工作使速度加倍。

來源

2012-02-22 18:32:15

您的代碼做了比需要更多的工作。您只需要一個布爾值數組，兩個循環來標記非素數，另一個循環可以打印素數的索引號。就像這樣：

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 + " "); 
}

來源

2012-02-22 20:13:07

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*/

來源

2016-12-30 04:41:46 Asish

在java中提高Eratosthenes代碼的效率

回答

相關問題