Task

Write a program which counts up from   1,   displaying each number as the multiplication of its prime factors.

For the purpose of this task,   1   (unity)   may be shown as itself.



Example

      2   is prime,   so it would be shown as itself.

      6   is not prime;   it would be shown as   



2
×
3


{\displaystyle 2\times 3}

.
2144   is not prime;   it would be shown as   



2
×
2
×
2
×
2
×
2
×
67


{\displaystyle 2\times 2\times 2\times 2\times 2\times 67}

.



Related tasks

   prime decomposition
   factors of an integer
   Sieve of Eratosthenes
   primality by trial division
   factors of a Mersenne number
   trial factoring of a Mersenne number
   partition an integer X into N primes


#include <stdio.h>
#include <stdlib.h>
 
typedef unsigned long long ULONG;
 
ULONG get_prime(int idx)
{
        static long n_primes = 0, alloc = 0;
        static ULONG *primes = 0;
        ULONG last, p;
        int i;
 
        if (idx >= n_primes) {
                if (n_primes >= alloc) {
                        alloc += 16; /* be conservative */
                        primes = realloc(primes, sizeof(ULONG) * alloc);
                }
                if (!n_primes) {
                        primes[0] = 2;
                        primes[1] = 3;
                        n_primes = 2;
                }
 
                last = primes[n_primes-1];
                while (idx >= n_primes) {
                        last += 2;
                        for (i = 0; i < n_primes; i++) {
                                p = primes[i];
                                if (p * p > last) {
                                        primes[n_primes++] = last;
                                        break;
                                }
                                if (last % p == 0) break;
                        }
                }
        }
        return primes[idx];
}
 
int main()
{
        ULONG n, x, p;
        int i, first;
 
        for (x = 1; ; x++) {
                printf("%lld = ", n = x);
 
                for (i = 0, first = 1; ; i++) {
                        p = get_prime(i);
                        while (n % p == 0) {
                                n /= p;
                                if (!first) printf(" x ");
                                first = 0;
                                printf("%lld", p);
                        }
                        if (n <= p * p) break;
                }
 
                if (first)      printf("%lld\n", n);
                else if (n > 1) printf(" x %lld\n", n);
                else            printf("\n");
        }
        return 0;
}