Discussion on: Daily Challenge #7 - Factorial Decomposition

View post

Here is a FORTRAN 90 answer (the module and an example program):

MODULE decompose

IMPLICIT NONE

CONTAINS

SUBROUTINE decomp(n,primes,powers,factorial)
    INTEGER, INTENT(IN)                     :: n
    INTEGER, ALLOCATABLE, INTENT(OUT)       :: primes(:),powers(:)
    INTEGER, INTENT(OUT)                    :: factorial
    INTEGER                                 :: i,j,m,current
    INTEGER, DIMENSION(25)                  :: lowPrimes

    DATA lowPrimes /2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97/

    IF (n.GT.100) THEN !can't handle a too big number
        PRINT *, "Choose a number less than 100"
        RETURN
    END IF

    m=COUNT(lowPrimes.LE.n)  !how many integers less or equal to n

    !initial values
    ALLOCATE(primes(m),powers(m))
    primes=lowPrimes(1:m)
    powers=0 
    factorial = 1

    !decomposing n! number by number
    DO i=2,n
        factorial = factorial * i
        current=i
      DO j=1,m
        IF (MOD(current , primes(j)) .EQ. 0) THEN
            current = INT(current / primes(j))
            powers(j) = powers(j) +1
        END IF
        IF (current.EQ.1) EXIT ! we are done decomposing i
      END DO !j
    END DO !i

END SUBROUTINE decomp

END MODULE decompose


PROGRAM testDecompose

    USE decompose
    IMPLICIT NONE

    INTEGER                     :: myInt,m,i
    INTEGER, ALLOCATABLE        :: pr(:),po(:)
    INTEGER                     :: fa

    myInt = 12
    CALL decomp(n=myInt,primes=pr,powers=po,factorial=fa)

    !printing the result:
    WRITE (*,"(i3,a4,i12,a3)",advance='no') myInt,"! = ",fa," = "
    m = SIZE(pr)
    DO i=1,m
        IF (po(i).GT. 0) WRITE(*,"(i2,a1,i2)" , advance='no') pr(i),"^",po(i)
        IF (i.LT.m) WRITE(*,"(a3)" , advance='no') " + "
    END DO

    PRINT *," "
END PROGRAM testDecompose

The result looks like:
12! = 479001600 = 2^ 6 + 3^ 4 + 5^ 2 + 7^ 1 + 11^ 1

Note: I hard coded n=12 but I could made n be read from the command line