[GO] Finden Sie die Primfaktorisierung der Leistung

Motivation

Wenn Sie beispielsweise versuchen, eine große Anzahl von Potenzen direkt auf einem Computer zu verarbeiten, können 32 Bit nur bis zu 12 Potenzen ausdrücken, sodass eine kleine Anzahl plötzlich eine Berechnung mit mehreren Längen erfordert.

Zum Beispiel wird $ 12! = 1 \ times2 \ times3 \ times4 \ times5 \ times6 \ times7 \ times8 \ times9 \ times10 \ times11 \ times12 $ in $ = 2 ^ {10} \ times3 ^ 5 \ times5 ^ zerlegt Es kann auch als 2 \ times7 ^ 1 \ times11 ^ 1 $ ausgedrückt werden.

Algorithmus

Die Nummer jeder Primzahl, die erscheint, wenn der Produktfaktor in Primfaktoren zerlegt wird, kann leicht wie folgt erhalten werden.

$ 12! = 1 \ times2 \ times3 \ times4 \ times5 \ times6 \ times7 \ times8 \ times9 \ times10 \ times11 \ times12 $ hat ein Vielfaches von $ 2 $ erscheint $ \ lfloor12 / 2 \ rfloor = 6 $ times, $ 2 ^ Ein Vielfaches von 2 $ erscheint $ \ lfloor12 / 2 ^ 2 \ rfloor = 3 $ mal, und ein Vielfaches von $ 2 ^ 3 $ erscheint $ \ lfloor12 / 2 ^ 3 \ rfloor = 1 $ mal. Diese $ 6 + 3 + 1 $ ist die Zahl von $ 2 $, wenn $ 12! $ Faktorisiert wird.

Gleiches gilt für $ 3 $, dh $ \ lfloor12 / 3 \ rfloor + \ lfloor12 / 3 ^ 2 \ rfloor = 5 $.

Nachtrag 28.08.2014 Es scheint, dass eine Verallgemeinerung davon manchmal "Legendres Theorem" genannt wird.

Factorial(Wikipedia)

Adrien-Marie Legendre found that the multiplicity of the prime p occurring in the prime factorization of n! can be expressed exactly as $\sum_{i=1}^{\infty} \left \lfloor \frac{n}{p^i} \right \rfloor$

Ende des Postskripts

Von diesen scheint es, dass es durch das folgende Verfahren erforderlich sein wird. Um die Primfaktorisierung von $ n! $ Zu finden, benötigen Sie zunächst eine Liste von Primzahlen bis zu $ n $. Machen Sie dies also mit dem Eratostenes-Sieb. Wenn Sie dann den Quotienten dieser Primzahlen in der ersten Potenz, den Quotienten der Quadrate usw. finden, ist die Summe davon die erforderliche Anzahl von Primzahlen.

Da wir ein Array von $ n $ -Elementen für das Sieben vorbereitet haben, gibt es Einschränkungen aufgrund der Speicherkapazität. Wenn es sich jedoch um eine Sprache handelt, die Verzögerungen auswerten kann, kann sie beschrieben werden, ohne Speicher zu verschwenden, sodass dies vorteilhaft erscheint. Ich werde.

Code

factfact.c

#include <stdio.h>

void
factfact(int n) {
  int prime[n+1];
  int i, j;

  for (i = 2; i <= n; i++) {
    prime[i] = 1;
  }
  for (i = 2; i <= n; i++) {
    if (prime[i]) {
      for (j = i*2; j <= n; j += i) {
        prime[j] = 0;
      }
    }
  }
  for (i = 2; i <= n; i++) {
    if (prime[i]) {
      prime[i] = 0;
      for (j = i; j <= n; j *= i) {
        prime[i] += n/j;
      }
      printf("%d^%d\n", i, prime[i]);
    }
  }
  printf("\n");
}

int
main(void) {
  factfact(12);
  factfact(1000000);
  return 0;
}