Trouvez la factorisation première de la puissance

Motivation

Si vous essayez de gérer un grand nombre de puissances directement sur un ordinateur, par exemple, 32 bits ne peuvent exprimer que jusqu'à 12 puissances, donc un petit nombre nécessite soudain un calcul de longueur multiple.

Cependant, par exemple, $ 12! = 1 \ times2 \ times3 \ times4 \ times5 \ times6 \ times7 \ times8 \ times9 \ times10 \ times11 \ times12 $ est factorisé en $ = 2 ^ {10} \ times3 ^ 5 \ times5 ^ Il peut également être exprimé par 2 \ times7 ^ 1 \ times11 ^ 1 $.

algorithme

Le nombre de chaque nombre premier qui apparaît lorsque le multiplicateur est décomposé en facteurs premiers peut être facilement obtenu comme suit.

$ 12! = 1 \ times2 \ times3 \ times4 \ times5 \ times6 \ times7 \ times8 \ times9 \ times10 \ times11 \ times12 $ a un multiple de $ 2 $ apparaissant $ \ lfloor12 / 2 \ rfloor = 6 $ fois, $ 2 ^ Un multiple de 2 $ apparaît $ \ lfloor12 / 2 ^ 2 \ rfloor = 3 $ fois, et un multiple de $ 2 ^ 3 $ apparaît $ \ lfloor12 / 2 ^ 3 \ rfloor = 1 $ fois. Ce $ 6 + 3 + 1 $ est le nombre de $ 2 $ lorsque $ 12! $ Est factorisé.

La même chose est vraie pour $ 3 $, soit $ \ lfloor12 / 3 \ rfloor + \ lfloor12 / 3 ^ 2 \ rfloor = 5 $.

Postscript 28/08/2014 Il semble qu'une généralisation de ceci soit parfois appelée "Théorème de Legendre".

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$

Fin du post-scriptum

De ceux-ci, il semble qu'il sera requis par la procédure suivante. Pour trouver la factorisation première de $ n! $, Vous avez d'abord besoin d'une liste de nombres premiers jusqu'à $ n $, alors faites-le avec le tamis Eratostenes. Ensuite, si vous trouvez le quotient de ces nombres premiers dans la première puissance, le quotient des carrés, etc., leur somme est le nombre requis de nombres premiers.

Puisque nous avons préparé un tableau d'éléments $ n $ pour le tamisage, il y aura des restrictions dues à la capacité mémoire, mais cela semble avantageux car il est possible de décrire sans gaspiller de mémoire si le langage peut évaluer le délai Je vais.

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