Распространение длинных чисел на простые множители

Question

Я хотел бы распространять большие числа на простые коэффициенты. Для того, чтобы сделать что Im используя свою версию Решето Эратосфена (в основном я, сохраняя наименьший простой множитель каждого числа в диапазоне в массиве)

 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 und error (в функциях main и inPrimeFactors), и я не совсем уверен, почему. Не могли бы вы помочь мне ?

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 слишком велик, то значение будет переполнение, и вы получите другой индекс из одной вы предназначенных, неправильного индекса. Я думаю, вы сделали это приведение, чтобы исправить ошибку компилятора, но это не имеет смысла. Использование переменной long в качестве индекса массива, отлитая от int, может работать только в том случае, если значение действительно находится в пределах диапазона int. В этом случае индексная переменная должна быть объявлена ​​как int, а не как long. Но это не ваш случай, так как вы хотите поддерживать очень большие числа.

Но даже если вы можете использовать long в качестве индекса массива, будет ли на вашем компьютере достаточно памяти для хранения такого большого массива? Сомневаюсь. Если вы хотите использовать такое большое сито, вам нужно будет создать пользовательский тип данных, например, что:

• это позволяет длинные индексы
• он хранит данные где-то (вероятно, на диске), когда он не вписывается в память

Или вы можете рассчитать простые коэффициенты без использования сита. Смотрите этот другой ответ, например: https://stackoverflow.com/a/12252237/641955