Atkin的篩子返回數組...帶有無效索引 - Java

因此，我制定了一個sieve of Atkin算法來生成素數（用於項目歐拉問題）。它返回一個名爲primes的素數數組（int []）。問題是，無論何時我嘗試從某個索引訪問該數組（我在main方法中這樣做）時，它都會拋出一個異常（java.lang.ArrayIndexOutOfBounds）。請幫助（如果您認爲我的邏輯與仙女分開，並且有更簡單的方法可以做到這一點，請告訴我）！Atkin的篩子返回數組...帶有無效索引 - Java

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

public class SieveOfAtkin { 
    public static void main(String[] stuff) { 
     int limit = getInt("Limit?"); 
     int[] p = getPrimes(limit); 
     for(int i = 0; i < p.length; i++) { 
      System.out.println(p[i]); 
     } 
    } 
    public static int[] getPrimes(int limit) { 
     boolean[] isPrime = new boolean[limit + 1]; 
     double sqrt = Math.sqrt(limit); 
     int n = 0; 
     for(int i = 0; i < limit + 1; i++) { 
      isPrime[i] = false; 
     } 
     for(int x = 0; x < sqrt; x++) { 
      for(int y = 0; y < sqrt; y++) { 
       n = 4 * x * x + y * y; 
       if(n <= limit && (n % 12 == 1 || n % 12 == 5)) { 
        isPrime[n] = !isPrime[n]; 
       } 
       n = 3 * x * x + y * y; 
       if(n <= limit && n % 12 == 7) { 
        isPrime[n] = !isPrime[n]; 
       } 
       n = 3 * x * x - y * y; 
       if(n <= limit && n % 12 == 11 && x > y) { 
        isPrime[n] = !isPrime[n]; 
       } 
      } 
     } 
     for(int i = 5; i < sqrt; i++) { 
      if(isPrime[i]) { 
       for(int j = i * i; j < limit; j = j + (i * i)) { 
        isPrime[j] = false; 
       } 
      } 
     } 
     int count = 0; 
     for(int i = 0; i < isPrime.length; i++) { 
      if(isPrime[i]) { 
       count++; 
      } 
     } 
     int[] primes = new int[count]; 
     int found = 0; 
     if (limit > 2) { 
      primes[found++] = 2; 
     } 
     if (limit > 3) { 
      primes[found++] = 3; 
     } 
     for (int p = 5; p <= limit; p += 2) { 
      if (isPrime[p]) { 
       primes[found++] = p; 
      } 
     } 
     return primes; 
    } 
public static int getInt(String prompt) { 
    System.out.print(prompt + " "); 
    int integer = input.nextInt(); 
    input.nextLine(); 
    return integer; 
} 
}

來源

2012-06-25 Bluefire

您的代碼鏈接不會轉到任何Java代碼。請在此處填寫簡短但完整的程序。 –

哎呀，對不起，我的壞D： – Bluefire

請注意，您提供的代碼也不會編譯。爲什麼不使用命令行參數？將第一行更改爲'int limit = Integer.parseInt（stuff [0]）;'並刪除您的'getInt'方法。 –

有沒有這樣的事情，「數組索引無效」。如果你正在訪問陣列，並且你得到了一個ArrayIndexOutOfBounds，那麼你要麼使用負向索引，要麼這個陣列沒有你想象的那麼大。調試您的代碼以找出實際陣列的長度（與array.length），並將其與您預期的相比較。

編輯：好的，現在我們已經得到了代碼，我們可以看到什麼是錯的。當你計算出陣列有多大時，你不計算值2和3 - 但當你填寫primes時，你的是。因此primes是兩個值太短。

您可以通過將isPrime[2]和isPrime[3]設置爲true來解決此問題。然後，您不需要你早些時候limit > 2等檢查 - 只是遍歷的primes全：

// After removing the special cases for 2 and 3 before this loop... but setting 
// isPrime[2] and isPrime[3] to true 
for (int p = 2; p <= limit; p++) { 
    if (isPrime[p]) { 
     primes[found++] = p; 
    } 
}

來源

2012-06-25 19:19:36

好的，我上傳了代碼。我讓我的程序告訴我'count'變量的大小，也就是數組的長度，即24。所以我不知道爲什麼它給了我一個無效的索引，*特別是*如果訪問它的循環是'for（int i = 0; i Bluefire

您可以嘗試將該語句切換爲for（int prime：p）System.out.println（prime）;在循環。這將保證它只會打印有效的引用。 – WLPhoenix

@Bluefire：這不是拋出異常的部分。您需要注意堆棧跟蹤。看看我的編輯有什麼問題。 –

你的問題是，你標記1爲一個素數，但使用isPrime數組中沒有2和3，所以當你計算你的計數關閉的素數。然後，當你開始填充你的素數組時，你不檢查素數2和3的isPrimes數組，而是假設他們已經被正確計算並將它們標記在素數組中，然後開始添加其餘的素數（現在是一個太多了）。

如果你添加了一些調試到你的循環，你可以計算素數的數量並填充素數組，你應該很容易找到它。

來源

2012-06-25 20:03:34

Atkin的篩子返回數組...帶有無效索引 - Java

回答

相關問題