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


count_primes = (max) ->
  # Count through the natural numbers and give their prime
  # factorization.  This algorithm uses no division.
  # Instead, each prime number starts a rolling odometer
  # to help subsequent factorizations.  The algorithm works similar
  # to the Sieve of Eratosthenes, as we note when each prime number's
  # odometer rolls a digit.  (As it turns out, as long as your computer
  # is not horribly slow at division, you're better off just doing simple
  # prime factorizations on each new n vs. using this algorithm.)
  console.log "1 = 1"
  primes = []
  n = 2
  while n <= max
    factors = []
    for prime_odometer in primes
      # digits are an array w/least significant digit in
      # position 0;  for example, [3, [0]] will roll as
      # follows:
      #    [0] -> [1] -> [2] -> [0, 1]
      [base, digits] = prime_odometer
      i = 0
      while true
        digits[i] += 1
        break if digits[i] < base
        digits[i] = 0
        factors.push base
        i += 1
        if i >= digits.length
          digits.push 0
 
    if factors.length == 0
      primes.push [n, [0, 1]]
      factors.push n
    console.log "#{n} = #{factors.join('*')}"
    n += 1
 
  primes.length
 
num_primes = count_primes 10000
console.log num_primes