quinta-feira, 23 de outubro de 2014

Fatorial revisitado IV

Encontrei uma maneira ainda mais simples e rápida e de calcular um fatorial a partir dos primos que o compõem.

Para um fatorial n! é preciso
  1. Calcular, para cada primo p menor que n, a soma (s) das divisões de n pelas potências (q) de p menores que n;
  2. n! é a multiplicação de todos os ps.
Então, para 10!, teremos:
  • 2^(10/2 + 10/4 + 10/8) = 2^(5+2+1)=2^8
  • 3^(10/3 + 10/9) = 3^(3+1) = 3^4
  • 5^(10/5) = 5^2
  • 7^(10/7) = 7^1
Logo, n! = 2^8*3^4*5^2*7 = 3628800.

import java.math.BigInteger;

public class Factorial {

  public static BigInteger f(int n) {
    int m=n+1;
    int[] s=new int[m];
    for(int i=2; i<=m/2; i++) {
      if(s[i]!=-1) {
        //Marcar todos os múltiplos
        for(int p=i+i; p<m; p+=i) {
          s[p]=-1;
        }
        //Calcular soma de expoentes até a maior potência anterior a n
        for(int q=i; q<=n; q=q*i) {
          s[i]+=n/q;
        }
      }
    }
    BigInteger f=BigInteger.ONE;
    for(int k=2; k<m; k++) {
      int pk=s[k];
      if(pk>=0) {
        if(k>2) {
          System.out.print("*");
        }
        if(pk<2) {
          System.out.print(k);
          f=f.multiply(BigInteger.valueOf(k));
        } else {
          System.out.print(k+"^"+pk);
          f=f.multiply(BigInteger.valueOf(k).pow(pk));
        }
      }
    }
    return f;
  }
    
  public static void main(String... args) {
    for(int i=2; i<20; i++) {
      System.out.printf("%d! = ", i);
      BigInteger f1=f(i);
      System.out.printf(" = %d\n", f1);
    }
  }
 }
Se eu já tivesse uma lista de primos guardada, o código seria ainda mais simples.

Nenhum comentário:

Postar um comentário