將長數字分解爲素數因子

Question

我想將大數分解爲素數因子。要做到這一點即時通訊使用我的版本的埃拉托色尼篩（基本上我每天保持數的最小素因子的範圍內，在陣列）

 protected final static int PowOf2= 21; 
     protected final static int[] Sieve = new int[(int) Math.pow(2,PowOf2)]; 
     protected final static int range = (int) Math.pow(2,PowOf2); //range of long types 
     static int a=0; //counter 


     public static void init(long n){ 
      for(int i=0; i<range-1; i++){ 
       Sieve[i]=i; //at first every number is equal to it's index 
      } 
      for(int i = 2; i*i <= range-1; i++) 
      { 
       if (Sieve[i] == i){ 
        for (int j = 2 * i ; j <= range-1; j += i) 
        { 
         Sieve[j] = i; //after that every number(index) has a smallest prime factor assigned to it 
        } 
       } 

      } 
     } 

然後我用這個數組來給出數除以以素因子

的

public static long[] intoPrimeFactors (long n){ 
     long[] array = new long[range-1]; 

     while(!isPrime(n)){ 
      array[a]=Sieve[(int)n]; //here's an error 
      n/=Sieve[(int) n]; 
      a++; 
     } 
     array[a]=n; 

     return array; 


    } 

在主我printig了所有的因素

public static void main(String[] args){ 
     long n=new Long(args[0]); 
     init(Math.abs(n)); 
     long[] array = intoPrimeFactors(Math.abs(n)); //here's an error 
     System.out.print(n+" = "); 

     if(n<0){ 
      n=Math.abs(n); 
      System.out.print("-1*"); 
     } 

     for(int i=0;i<=a;i++){ 
      if(i!=a)System.out.print(array[i]+"*"); 
      else System.out.print(array[i]); 
     } 

    } 

而且它適用於小數字（INT），但是當我在類似9223371331鍵入我得到ArrayOutOfBo就好了和錯誤（在函數主要和intoPrimeFactors），我不知道爲什麼。你可以幫幫我嗎 ？

Answer 1

這是你如何初始化Sieve：

protected final static int[] Sieve = new int[(int) Math.pow(2,PowOf2)]; 

它的尺寸是：2097152

然後在intoPrimeFactors， 這段代碼將爲數來執行你給作爲輸入：

while(!isPrime(n)){ 
    array[a]=Sieve[(int)n]; //here's an error 
    n/=Sieve[(int) n]; 
    a++; 
} 

如果有足夠大的非素數輸入，它將嘗試訪問超出容量Sieve，res在ArrayOutOfBound中排除。異常中的錯誤消息也會告訴您Sieve的確切索引太大。

那麼你能做什麼？首先，有一些東西你不能這樣做，這是這樣的：

Sieve[(int) n] 

如果n太大，該值將溢出，你會得到你想要的一個，一個錯誤的索引不同的索引。我想你做了這個工作來解決編譯器錯誤，但它沒有任何意義。如果數值實際上在int的範圍內，則使用long變量作爲數組索引，可以將其轉換爲int。在這種情況下，索引變量應該首先聲明爲int，而不是long。但是，這不是你的情況，因爲你想支持非常大的數字。

但即使您可以使用long作爲數組索引，您的計算機是否有足夠的內存來容納如此大的數組？我不信。如果你想用這樣一個大篩子，你需要創建一個自定義的數據類型，使得：

• 它允許長期指標
• 在別的地方（可能在磁盤上）存儲數據時，它不適合內存

或者您可以不使用篩子計算素因子。看到這個其他答案，例如：https://stackoverflow.com/a/12252237/641955