将长数字分解为素数因子

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