премьер факторизации больших чисел, чем Int

Question

Эта программа делает простые множители чисел в С.

#include <stdio.h> 

int main(void) { 
    int number, i, p, n, factors, count; 
    int numbers[1000000]; 
    int counter = 0; 
    char text[100000]; 

    for (count = 0; count < 1000000; count++) { 
     fgets(text, 10000000, stdin); 
     if (sscanf(text, "%d", &number) == 1) { 
      if (number == 0) 
       break; 
      numbers[count] = number; 
     } else { 
      numbers[count] = 0; 
     } 
    } 
    counter = 0; 
    for (i = 0; i < count; i++) { 
     if ((numbers[i] < 0) || (numbers[i] == 0)) { 
      fprintf(stderr, "Error: Wrong Input!\n"); 
      return 100; 
      break; 
     } 
     number = numbers[i]; 
     printf("Prime factorization of nubmer %d is:\n", number); 
     factors = 0; 
     for (p = 2; p * p <= number; p += 1 + (p & 1)) { 
      if (number % p == 0) { 
       n = 0; 
       factors++; 
       do { 
        number /= p; 
        n++; 
       } while (number % p == 0); 
       if (n == 1) { 
        printf("%d ", p); 
        ++counter; 
       } else 
        printf("%d^%d ", p, n); 
       ++counter; 

       if (count > 0 && number != 1) 
        printf("x "); 
      } 
     } 
     if (factors == 0 || number != 1) 
      printf("%d", number); 
     printf("\n"); 
    } 
    return 0; 
} 

Эта программа прекрасно работает для чисел, меньших 10 . Но мой вопрос заключается в том, есть ли способ сделать эту программу даже для чисел вроде 10 . Я знаю, что int будет недостаточно, но когда я попытался использовать long int, это не сработало. Также я слышал что-то о malloc, но я продолжаю не реализовывать (понимать) его.

Answer 1

Вы можете использовать длинный длинный. Но, вероятно, реальная проблема заключается в том, что для выполнения факторизации по числам потребуется недолгое время, чтобы не разбить нормальный int. Например. вы пытаетесь разложить простое число в диапазоне 10^12, тогда вам нужно будет сделать около 10^6 делений.

Дело в том, что malloc не поможет вам в решении этой проблемы вообще, потому что даже более крупные значения потребуют еще больше времени для факторизации. Итак, если вы хотите знать, как работает malloc, я предлагаю открыть для этого отдельный вопрос.

Answer 2

Ниже приведена переделка кода с использованием unsigned long long. (Я бросил файл, чтобы это было минимальным.) Работает ли это для вашей цели, зависит от того, как ваша система определяет long long (в моей системе это 64 бита). Я также переделал формат вывода, чтобы быть совместимым с постфикса нотация Unix dc командования, так что я мог бы легко проверить, если результаты были правильными:

#include <stdio.h> 
#include <stdlib.h> 

int main() { 

    unsigned long long large = 18446744073709551615ULL; // 2^64 - 1 

    for (unsigned long long counter = large - 1000; counter < large; counter++) { 

     unsigned long long number = counter; 

     printf("Prime factorization of %llu is:", number); 

     unsigned long factors = 0; 

     for (unsigned long long p = 2; p * p <= number; p += 1 + (p & 1)) { 

      if (number % p == 0) { 
       factors++; 

       unsigned long n = 0; 

       do { 
        number /= p; 
        n++; 
       } while (number % p == 0); 

       if (n == 1) { 
        printf(" %llu", p); 
       } 
       else { 
        printf(" %llu %lu ^", p, n); 
       } 

       if (number != 1 && factors > 1) { 
        printf(" *"); 
       } 
      } 
     } 

     if (factors == 0 || number != 1) { 
      factors++; 

      printf(" %llu", number); 
     } 

     if (factors > 1) { 
      printf(" *"); 
     } 

     printf("\n"); 
    } 

    return 0; 
} 

SAMPLE OUTPUT

% ./a.out 
Prime factorization of 18446744073709550615 is: 5 563 * 751 * 8725722280871 * 
Prime factorization of 18446744073709550616 is: 2 3^3 * 41 * 7523 * 8243 * 14479 * 20879 * 
Prime factorization of 18446744073709550617 is: 79 557 * 419215600611539 * 
Prime factorization of 18446744073709550618 is: 2 2298974999 * 4011949691 * 
Prime factorization of 18446744073709550619 is: 3 3^1008659 * 677347590683 * 
Prime factorization of 18446744073709550620 is: 2 2^5 * 7 * 149 * 233 * 3795329598449 * 
Prime factorization of 18446744073709550621 is: 11 23 * 72912031911895457 * 
Prime factorization of 18446744073709550622 is: 2 3 * 479909 * 6406334004193 * 
Prime factorization of 18446744073709550623 is: 3421377637 5391612979 * 
Prime factorization of 18446744073709550624 is: 2 5^61 * 593 * 1699 * 9379762391 * 
Prime factorization of 18446744073709550625 is: 3 5 4^* 13 * 756789500459879 * 
Prime factorization of 18446744073709550626 is: 2 3743461 * 2463862195133 * 
Prime factorization of 18446744073709550627 is: 7 1283 * 4339 * 627089 * 754877 * 
Prime factorization of 18446744073709550628 is: 2 2^3 2^* 101 * 293 * 42751 * 405025111 * 
Prime factorization of 18446744073709550629 is: 17 43 * 613 * 66457 * 619442699 * 
... 

Это работает медленнее, но достаточно , Вы можете нажать это еще на некоторых системах путем замены unsigned long long для uint128_t, которые поддерживают некоторые компиляторы несколько: (. И до тех unsigned long деклараций unsigned long long)

typedef unsigned __int128 uint128_t; 

Вы должны были бы поставить номер печати процедуры для uint128_t типа поскольку printf() не будет обращаться с ними напрямую. Я пробовал это с приведенным выше кодом, и это сработало:

Prime factorization of 340282366920938463426481119284349108124 is: 2 2^31 * 6131 * 7654271 * 21163829 * 21491837 * 128562653437 * 

% dc 
2 2^31 * 6131 * 7654271 * 21163829 * 21491837 * 128562653437 * p 
340282366920938463426481119284349108124 

Но я никогда не видел, чтобы он выполнял более одного номера во время его запуска!

Answer 3

Факторы, накладывающие большие суммы, как правило, требуют более тонкого подхода, чем простое пробное подразделение. Вот возможный набросок:

1. Составьте список всех простых чисел, скажем, 25 000.
2. Используйте этот список, чтобы удалить все основные факторы ниже 25 000.
3. Если есть остаток> 1, тогда проверьте, является ли остаток простым с тестом Миллера-Рабина или аналогичным.
4. Если остаток является простым, то вы нашли последний коэффициент.
5. Если остаток не является простым, тогда вам придется его разложить. Я боюсь, это неизбежно будет медленным.

Answer 4

Использование типа unsigned long long для number и главные факторы приведут вас к 10 по цене более длительного времени вычислений.

Обратите внимание, однако, что определение большого локального массива с автоматическим хранилищем может вызвать проблемы, особенно когда размер достигает 8 мегабайт, как в случае с типом unsigned long long (этот тип не менее 64-битного). Выделение его из кучи более безопасно.

Здесь адаптированный вариант кода:

#include <stdio.h> 
#include <stdlib.h> 

#define NUMBER_MAX 1000000 

int main(void) { 
    unsigned long long *numbers; 
    unsigned long long number, p; 
    int i, n, factors, count; 
    char text[100]; 

    numbers = calloc(NUMBER_MAX, sizeof(*numbers)); 
    if (numbers == NULL) { 
     printf("cannot allocate number array\n"); 
     return 1; 
    } 

    for (count = 0; count < NUMBER_MAX; count++) { 
     if (!fgets(text, sizeof text, stdin)) { 
      break; 
     } 
     if (sscanf(text, "%llu", &number) == 1 && number > 0) { 
      numbers[count] = number; 
     } else { 
      fprintf(stderr, "Error: Wrong Input!\n"); 
      return 100; 
     } 
    } 
    for (i = 0; i < count; i++) { 
     number = numbers[i]; 
     printf("Prime factorization of nubmer %llu is:\n", number); 
     factors = 0; 
     for (p = 2; p < 0x100000000 && p * p <= number; p += 1 + (p & 1)) { 
      if (number % p == 0) { 
       n = 0; 
       factors++; 
       do { 
        number /= p; 
        n++; 
       } while (number % p == 0); 
       if (n == 1) { 
        printf("%llu ", p); 
       } else { 
        printf("%llu^%d ", p, n); 
       } 
       if (number != 1) { 
        printf("* "); 
       } 
      } 
     } 
     if (factors == 0 || number != 1) { 
      printf("%llu", number); 
     } 
     printf("\n"); 
    } 
    free(numbers); 
    return 0; 
}