Primfaktorzerlegung von größeren Zahlen als int

Question

Dieses Programm macht Primfaktorzerlegung von Zahlen in C.

#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; 
} 

Dieses Programm arbeitet für Zahlen Fein kleiner als 10 . Aber meine Frage ist, ob es eine Möglichkeit gibt, dieses Programm auch für Zahlen wie 10 zu machen. Ich weiß, dass Int nicht genug wäre, aber wenn ich zum Beispiel Long Int versuchte, hat es nicht funktioniert. Ich habe auch etwas über Malloc gehört, aber ich habe es immer noch nicht umgesetzt.

Answer 1

Sie können lange verwenden. Aber wahrscheinlich ist das wirkliche Problem, dass es eine veeeeerrrryyy lange Zeit dauern wird, die Faktorisierung auf Zahlen zu machen, die nicht in einen normalen int passen. Z.B. Sie versuchen, eine Primzahl im Bereich 10^12 zu faktorisieren, dann müssen Sie etwa 10^6 Divisionen machen.

Die Sache mit malloc wird Ihnen bei diesem Problem überhaupt nicht helfen, denn selbst größere Werte brauchen noch länger zu faktorisieren. Also, wenn Sie wissen möchten, wie malloc funktioniert, schlage ich vor, eine separate Frage dafür zu öffnen.

Answer 2

Unten ist eine Überarbeitung des Codes mit unsigned long long. (Ich habe das Datei-Zeug geworfen, um dies auf ein minimales Beispiel zu beschränken.) Ob dies für Ihren Zweck funktioniert, hängt davon ab, wie Ihr System einen long long definiert (auf meinem System sind es 64 Bits). Ich umgestrickt auch das Ausgabeformat mit dem Unix dc Befehls des Postfixnotation kompatibel zu sein, damit ich einfach, wenn die Ergebnisse richtig waren überprüfen könnte:

#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 * 
... 

Diese langsamer läuft, aber vernünftig . Sie können dies auf einigen Systemen weiter vorantreiben unsigned long long für ein uint128_t durch Vertauschen der einig Compiler unterstützen etwas: (. Und bis die unsigned long Erklärungen zu unsigned long long)

typedef unsigned __int128 uint128_t; 

Sie müßten Anzahl Druckroutinen für den uint128_t Typen liefern als printf() wird nicht direkt mit ihnen umgehen. Ich habe versucht, dies mit dem obigen Code und es funktionierte:

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

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

Aber ich sah es nie mehr als eine Nummer zu vervollständigen, während es läuft!

Answer 3

Die Faktorisierung großer Zahlen erfordert in der Regel einen subtileren Ansatz als die einfache Testaufteilung. Hier ist eine mögliche Umrissmethode:

1. Erstellen Sie eine Liste aller Primzahlen bis zu sagen wir 25.000.
2. Verwenden Sie die Liste, um alle Primfaktoren unter 25.000 zu entfernen.
3. Wenn es einen Rest> 1 gibt, überprüfen Sie, ob der Rest mit einem Miller-Rabin-Test oder ähnlichem prime ist.
4. Wenn der Rest prim ist, dann haben Sie den letzten Faktor gefunden.
5. Wenn der Rest nicht prim ist, dann müssen Sie es faktorisieren. Das wird unweigerlich langsam sein, fürchte ich.

Answer 4

Mit Typ unsigned long long für number und die Primfaktoren sind Sie in 10 zum Preis von mehreren Rechenzeiten nehmen.

Beachten Sie jedoch, dass das Definieren eines großen lokalen Arrays mit automatischem Speicher zu Problemen führen kann, insbesondere bei einer Größe von 8 MB, wie es beim Typ unsigned long long der Fall ist (dieser Typ ist mindestens 64 Bit breit). Die Zuordnung vom Heap ist sicherer. Hier

ist eine angepasste Version des Codes:

#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; 
}