Count in factors

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$ may be shown as itself.

For examle, $2$ is prime, so it would be shown as itself. $6$ is not prime; it would be shown as $2\times 3$ . Likewise, 2144 is not prime; it would be shown as $2\times 2\times 2\times 2\times 2\times 67$ .

c.f. Prime decomposition

Category:Prime_Numbers

Ada

count.adb

<lang Ada>with Ada.Command_Line; with Ada.Text_IO;

procedure Count is

  type Number_List is array (Positive range <>) of Positive;

  function Decompose (N : Natural) return Number_List is
     Size : Natural := 0;
     M    : Natural := N;
     K    : Natural := 2;
  begin
     if N = 1 then
        return (1 => 1);
     end if;
     -- Estimation of the result length from above
     while M >= 2 loop
        M    := (M + 1) / 2;
        Size := Size + 1;
     end loop;
     M := N;
     -- Filling the result with prime numbers
     declare
        Result : Number_List (1 .. Size);
        Index  : Positive := 1;
     begin
        while N >= K loop -- Divisors loop
           while 0 = (M mod K) loop -- While divides
              Result (Index) := K;
              Index          := Index + 1;
              M              := M / K;
           end loop;
           K := K + 1;
        end loop;
        return Result (1 .. Index - 1);
     end;
  end Decompose;

  procedure Put (List : Number_List) is
  begin
     for Index in List'Range loop
        Ada.Text_IO.Put (Integer'Image (List (Index)));
        if Index /= List'Last then
           Ada.Text_IO.Put (" x");
        end if;
     end loop;
  end Put;

  N     : Natural := 1;
  Max_N : Natural := 15;

begin

  if Ada.Command_Line.Argument_Count = 1 then
     Max_N := Integer'Value (Ada.Command_Line.Argument (1));
  end if;
  loop
     Ada.Text_IO.Put (Integer'Image (N) & ": ");
     Put (Decompose (N));
     Ada.Text_IO.New_Line;
     N := N + 1;
     exit when N > Max_N;
  end loop;

end Count;</lang>

Output:

 1:  1
 2:  2
 3:  3
 4:  2 x 2
 5:  5
 6:  2 x 3
 7:  7
 8:  2 x 2 x 2
 9:  3 x 3
 10:  2 x 5
 11:  11
 12:  2 x 2 x 3
 13:  13
 14:  2 x 7
 15:  3 x 5

AutoHotkey

Translation of: D

<lang AutoHotkey>factorize(n){ if n = 1 return 1 if n < 1 return false result := 0, m := n, k := 2 While n >= k{ while !Mod(m, k){ result .= " * " . k, m /= k } k++ } return SubStr(result, 5) } Loop 22

  out .= A_Index ": " factorize(A_index) "`n"

MsgBox % out</lang>

Output:

1: 1
2: 2
3: 3
4: 2 * 2
5: 5
6: 2 * 3
7: 7
8: 2 * 2 * 2
9: 3 * 3
10: 2 * 5
11: 11
12: 2 * 2 * 3
13: 13
14: 2 * 7
15: 3 * 5
16: 2 * 2 * 2 * 2
17: 17
18: 2 * 3 * 3
19: 19
20: 2 * 2 * 5
21: 3 * 7
22: 2 * 11

BBC BASIC

<lang bbcbasic> FOR i% = 1 TO 20

       PRINT i% " = " FNfactors(i%)
     NEXT
     END
     
     DEF FNfactors(N%)
     LOCAL P%, f$
     IF N% = 1 THEN = "1"
     P% = 2
     WHILE P% <= N%
       IF (N% MOD P%) = 0 THEN
         f$ += STR$(P%) + " x "
         N% DIV= P%
       ELSE
         P% += 1
       ENDIF
     ENDWHILE
     = LEFT$(f$, LEN(f$) - 3)

</lang> Output:

         1 = 1
         2 = 2
         3 = 3
         4 = 2 x 2
         5 = 5
         6 = 2 x 3
         7 = 7
         8 = 2 x 2 x 2
         9 = 3 x 3
        10 = 2 x 5
        11 = 11
        12 = 2 x 2 x 3
        13 = 13
        14 = 2 x 7
        15 = 3 x 5
        16 = 2 x 2 x 2 x 2
        17 = 17
        18 = 2 x 3 x 3
        19 = 19
        20 = 2 x 2 x 5

C

Code includes a dynamically extending prime number list. The program doesn't stop until you kill it, or it runs out of memory, or it overflows. <lang C>#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;

}</lang>

Output:

1 = 1
2 = 2
3 = 3
4 = 2 x 2
5 = 5
6 = 2 x 3
7 = 7
8 = 2 x 2 x 2
9 = 3 x 3
10 = 2 x 5
11 = 11
12 = 2 x 2 x 3
13 = 13
14 = 2 x 7
.
.
.

C#

<lang csharp>using System; using System.Collections.Generic;

namespace prog { class MainClass { public static void Main (string[] args) { for( int i=1; i<=22; i++ ) { List<int> f = Factorize(i); Console.Write( i + ": " + f[0] ); for( int j=1; j<f.Count; j++ ) { Console.Write( " * " + f[j] ); } Console.WriteLine(); } }

public static List<int> Factorize( int n ) { List<int> l = new List<int>();

if ( n == 1 ) { l.Add(1); } else { int k = 2; while( n > 1 ) { while( n % k == 0 ) { l.Add( k ); n /= k; } k++; } } return l; } } }</lang>

CoffeeScript

<lang coffeescript>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</lang>

Common Lisp

Auto extending prime list: <lang lisp>(defparameter *primes*

 (make-array 10 :adjustable t :fill-pointer 0 :element-type 'integer))

(mapc #'(lambda (x) (vector-push x *primes*)) '(2 3 5 7))

(defun extend-primes (n)

 (let ((p (+ 2 (elt *primes* (1- (length *primes*))))))
   (loop for i = p then (+ 2 i)

while (<= (* i i) n) do (if (primep i t) (vector-push-extend i *primes*)))))

(defun primep (n &optional skip)

 (if (not skip) (extend-primes n))
 (if (= n 1) nil
     (loop for p across *primes* while (<= (* p p) n)

never (zerop (mod n p)))))

(defun factors (n)

 (extend-primes n)
 (loop with res for x across *primes* while (> n (* x x)) do

(loop while (zerop (rem n x)) do (setf n (/ n x)) (push x res)) finally (return (if (> n 1) (cons n res) res))))

(loop for n from 1 do

     (format t "~a: ~{~a~^ × ~}~%" n (reverse (factors n))))</lang>

Output:

1: 
2: 2
3: 3
4: 4
5: 5
6: 2 × 3
7: 7
8: 2 × 2 × 2
9: 9
10: 2 × 5
11: 11
12: 2 × 2 × 3
13: 13
14: 2 × 7
...

Without saving the primes, and not all that much slower (probably because above code was not well-written): <lang lisp>(defun factors (n)

 (loop with res for x from 2 to (isqrt n) do

(loop while (zerop (rem n x)) do (setf n (/ n x)) (push x res)) finally (return (if (> n 1) (cons n res) res))))

(loop for n from 1 do

     (format t "~a: ~{~a~^ × ~}~%" n (reverse (factors n))))</lang>

D

<lang d>int[] factorize(in int n) pure nothrow in {

   assert(n > 0);

} body {

   if (n == 1) return [1];
   int[] result;
   int m = n, k = 2;
   while (n >= k) {
       while (m % k == 0) {
           result ~= k;
           m /= k;
       }
       k++;
   }
   return result;

}

void main() {

   import std.stdio;
   foreach (i; 1 .. 22)
       writefln("%d: %(%d × %)", i, i.factorize());

}</lang>

Output:

1: 1
2: 2
3: 3
4: 2 × 2
5: 5
6: 2 × 3
7: 7
8: 2 × 2 × 2
9: 3 × 3
10: 2 × 5
11: 11
12: 2 × 2 × 3
13: 13
14: 2 × 7
15: 3 × 5
16: 2 × 2 × 2 × 2
17: 17
18: 2 × 3 × 3
19: 19
20: 2 × 2 × 5
21: 3 × 7

Alternative Version

Library: uiprimes

Library uiprimes is a homebrew library to generate prime numbers upto the maximum 32bit unsigned integer range 2^32-1, by using a pre-generated bit array of Sieve of Eratosthenes (a dll in size of ~256M bytes :p ).

<lang d>import std.stdio, std.math, std.conv, std.algorithm,

      std.array, std.string, import xt.uiprimes;

pragma(lib, "uiprimes.lib");

// function _factorize_ included in uiprimes.lib ulong[] factorize(ulong n) {

   if (n == 0) return [];
   if (n == 1) return [1];
   ulong[] res;
   uint limit = cast(uint)(1 + sqrt(n));
   foreach (p; Primes(limit)) {
       if (n == 1) break;
       if (0UL == (n % p))
           while((n > 1) && (0UL == (n % p ))) {
               res ~= p;
               n /= p;
           }
   }
   if (n > 1)
       res ~= [n];
   return res;

}

string productStr(T)(in T[] nums) {

   return nums.map!text().join(" x ");

}

void main() {

   foreach (i; 1 .. 21)
       writefln("%2d = %s", i, productStr(factorize(i)));

}</lang>

DWScript

<lang delphi>function Factorize(n : Integer) : String; begin

  if n <= 1 then
     Exit('1');
  var k := 2;
  while n >= k do begin
     while (n mod k) = 0 do begin
        Result += ' * '+IntToStr(k);
        n := n div k;
     end;
     Inc(k);
  end;
  Result:=SubStr(Result, 4);

end;

var i : Integer; for i := 1 to 22 do

  PrintLn(IntToStr(i) + ': ' + Factorize(i));</lang>

Output:

1: 1
2: 2
3: 3
4: 2 * 2
5: 5
6: 2 * 3
7: 7
8: 2 * 2 * 2
9: 3 * 3
10: 2 * 5
11: 11
12: 2 * 2 * 3
13: 13
14: 2 * 7
15: 3 * 5
16: 2 * 2 * 2 * 2
17: 17
18: 2 * 3 * 3
19: 19
20: 2 * 2 * 5
21: 3 * 7
22: 2 * 11

Euphoria

<lang euphoria>function factorize(integer n)

   sequence result
   integer k
   if n = 1 then
       return {1}
   else
       k = 2
       result = {}
       while n > 1 do
           while remainder(n, k) = 0 do
               result &= k
               n /= k
           end while
           k += 1
       end while
       return result
   end if

end function

sequence factors for i = 1 to 22 do

   printf(1, "%d: ", i)
   factors = factorize(i)
   for j = 1 to length(factors)-1 do
       printf(1, "%d * ", factors[j])
   end for
   printf(1, "%d\n", factors[$])

end for</lang>

Output:

1: 1
2: 2
3: 3
4: 2 * 2
5: 5
6: 2 * 3
7: 7
8: 2 * 2 * 2
9: 3 * 3
10: 2 * 5
11: 11
12: 2 * 2 * 3
13: 13
14: 2 * 7
15: 3 * 5
16: 2 * 2 * 2 * 2
17: 17
18: 2 * 3 * 3
19: 19
20: 2 * 2 * 5
21: 3 * 7
22: 2 * 11

Forth

<lang forth>: .factors ( n -- )

 2
 begin  2dup dup * >=
 while  2dup /mod swap
        if   drop  1+ 1 or    \ next odd number
        else -rot nip  dup . ." x "
        then
 repeat
 drop . ;

main ( n -- )

 ." 1 : 1" cr
 1+ 2 ?do i . ." : " i .factors cr loop ;

15 main bye</lang>

Fortran

Please find the example output along with the build instructions in the comments at the start of the FORTRAN 2008 source. Compiler: gfortran from the GNU compiler collection. Command interpreter: bash. The code writes j assertions which don't prove primality of the factors but does prove they are the factors.

This algorithm creates a sieve of Eratosthenes, storing the largest prime factor to mark composites. It then finds prime factors by repeatedly looking up the value in the sieve, then dividing by the factor found until the value is itself prime. Using the sieve table to store factors rather than as a plain bitmap was to me a novel idea.

<lang FORTRAN> !-*- mode: compilation; default-directory: "/tmp/" -*- !Compilation started at Thu Jun 6 23:29:06 ! !a=./f && make $a && echo -2 | OMP_NUM_THREADS=2 $a !gfortran -std=f2008 -Wall -fopenmp -ffree-form -fall-intrinsics -fimplicit-none f.f08 -o f ! assert 1 = */ 1 ! assert 2 = */ 2 ! assert 3 = */ 3 ! assert 4 = */ 2 2 ! assert 5 = */ 5 ! assert 6 = */ 2 3 ! assert 7 = */ 7 ! assert 8 = */ 2 2 2 ! assert 9 = */ 3 3 ! assert 10 = */ 2 5 ! assert 11 = */ 11 ! assert 12 = */ 3 2 2 ! assert 13 = */ 13 ! assert 14 = */ 2 7 ! assert 15 = */ 3 5 ! assert 16 = */ 2 2 2 2 ! assert 17 = */ 17 ! assert 18 = */ 3 2 3 ! assert 19 = */ 19 ! assert 20 = */ 2 2 5 ! assert 21 = */ 3 7 ! assert 22 = */ 2 11 ! assert 23 = */ 23 ! assert 24 = */ 3 2 2 2 ! assert 25 = */ 5 5 ! assert 26 = */ 2 13 ! assert 27 = */ 3 3 3 ! assert 28 = */ 2 2 7 ! assert 29 = */ 29 ! assert 30 = */ 5 2 3 ! assert 31 = */ 31 ! assert 32 = */ 2 2 2 2 2 ! assert 33 = */ 3 11 ! assert 34 = */ 2 17 ! assert 35 = */ 5 7 ! assert 36 = */ 3 3 2 2 ! assert 37 = */ 37 ! assert 38 = */ 2 19 ! assert 39 = */ 3 13 ! assert 40 = */ 5 2 2 2

module prime_mod

 ! sieve_table stores 0 in prime numbers, and a prime factor in composites.
 integer, dimension(:), allocatable :: sieve_table
 private :: PrimeQ

contains

 ! setup routine must be called first!
 subroutine sieve(n) ! populate sieve_table.  If n is 0 it deallocates storage, invalidating sieve_table.
   integer, intent(in) :: n
   integer :: status, i, j
   if ((n .lt. 1) .or. allocated(sieve_table)) deallocate(sieve_table)
   if (n .lt. 1) return
   allocate(sieve_table(n), stat=status)
   if (status .ne. 0) stop 'cannot allocate space'
   sieve_table(1) = 1
   do i=2,n
      if (sieve_table(i) .eq. 0) then
         do j = i*i, n, i
            sieve_table(j) = i
         end do
      end if
   end do
 end subroutine sieve

 subroutine check_sieve(n)
   integer, intent(in) :: n
   if (.not. (allocated(sieve_table) .and. ((1 .le. n) .and. (n .le. size(sieve_table))))) stop 'Call sieve first'
 end subroutine check_sieve

 logical function isPrime(p)
   integer, intent(in) :: p
   call check_sieve(p)
   isPrime = PrimeQ(p)
 end function isPrime

 logical function isComposite(p)
   integer, intent(in) :: p
   isComposite = .not. isPrime(p)
 end function isComposite

 logical function PrimeQ(p)
   integer, intent(in) :: p
   PrimeQ = sieve_table(p) .eq. 0
 end function PrimeQ

 subroutine prime_factors(p, rv, n)
   integer, intent(in) :: p ! number to factor
   integer, dimension(:), intent(out) :: rv ! the prime factors
   integer, intent(out) :: n ! number of factors returned
   integer :: i, m
   call check_sieve(p)
   m = p
   i = 1
   if (p .ne. 1) then
      do while ((.not. PrimeQ(m)) .and. (i .lt. size(rv)))
         rv(i) = sieve_table(m)
         m = m/rv(i)
         i = i+1
      end do
   end if
   if (i .le. size(rv)) rv(i) = m
   n = i
 end subroutine prime_factors

end module prime_mod

program count_in_factors

 use prime_mod
 integer :: i, n
 integer, dimension(8) :: factors
 call sieve(40)                ! setup
 do i=1,40
    factors = 0
    call prime_factors(i, factors, n)
    write(6,*)'assert',i,'= */',factors(:n)
 end do
 call sieve(0)                 ! release memory

end program count_in_factors </lang>

Go

<lang go>package main

import "fmt"

func main() {

   fmt.Println("1: 1")
   for i := 2; ; i++ {
       fmt.Printf("%d: ", i)
       var x string
       for n, f := i, 2; n != 1; f++ {
           for m := n % f; m == 0; m = n % f {
               fmt.Print(x, f)
               x = "×"
               n /= f
           }
       }
       fmt.Println()
   }

}</lang>

Output:

1: 1
2: 2
3: 3
4: 2×2
5: 5
6: 2×3
7: 7
8: 2×2×2
9: 3×3
10: 2×5
...

Groovy

<lang groovy>def factors(number) {

   if (number == 1) {
       return [1]
   }
   def factors = []
   BigInteger value = number
   BigInteger possibleFactor = 2
   while (possibleFactor <= value) {
       if (value % possibleFactor == 0) {
           factors << possibleFactor
           value /= possibleFactor
       } else {
           possibleFactor++
       }
   }
   factors

} Number.metaClass.factors = { factors(delegate) }

((1..10) + (6351..6359)).each { number ->

   println "$number = ${number.factors().join(' x ')}"

}</lang>

Output:

1 = 1
2 = 2
3 = 3
4 = 2 x 2
5 = 5
6 = 2 x 3
7 = 7
8 = 2 x 2 x 2
9 = 3 x 3
10 = 2 x 5
6351 = 3 x 29 x 73
6352 = 2 x 2 x 2 x 2 x 397
6353 = 6353
6354 = 2 x 3 x 3 x 353
6355 = 5 x 31 x 41
6356 = 2 x 2 x 7 x 227
6357 = 3 x 13 x 163
6358 = 2 x 11 x 17 x 17
6359 = 6359

Haskell

Using factorize function from the prime decomposition task, <lang haskell>import Data.List (intercalate)

showFactors n = show n ++ " = " ++ (intercalate " * " . map show . factorize) n</lang>

Output:

<lang haskell>Main> print 1 >> mapM_ (putStrLn . showFactors) [2..] 1 2 = 2 3 = 3 4 = 2 * 2 5 = 5 6 = 2 * 3 7 = 7 8 = 2 * 2 * 2 9 = 3 * 3 10 = 2 * 5 11 = 11 12 = 2 * 2 * 3 . . .

Main> mapM_ (putStrLn . showFactors) [2144..] 2144 = 2 * 2 * 2 * 2 * 2 * 67 2145 = 3 * 5 * 11 * 13 2146 = 2 * 29 * 37 2147 = 19 * 113 2148 = 2 * 2 * 3 * 179 2149 = 7 * 307 2150 = 2 * 5 * 5 * 43 2151 = 3 * 3 * 239 2152 = 2 * 2 * 2 * 269 2153 = 2153 2154 = 2 * 3 * 359 . . .

Main> mapM_ (putStrLn . showFactors) [121231231232155..] 121231231232155 = 5 * 11 * 419 * 5260630559 121231231232156 = 2 * 2 * 97 * 1061 * 294487867 121231231232157 = 3 * 3 * 3 * 131 * 34275157261 121231231232158 = 2 * 19 * 67 * 1231 * 38681033 121231231232159 = 121231231232159 121231231232160 = 2 * 2 * 2 * 2 * 2 * 3 * 5 * 7 * 7 * 5154389083 121231231232161 = 121231231232161 121231231232162 = 2 * 60615615616081 121231231232163 = 3 * 13 * 83 * 191089 * 195991 121231231232164 = 2 * 2 * 253811 * 119410931 121231231232165 = 5 * 137 * 176979899609 . . .</lang> The real solution seems to have to be some sort of a segmented offset sieve of Eratosthenes, storing factors in array's cells instead of just marks. That way the speed of production might not be diminishing as much.

Icon and Unicon

<lang Icon>procedure main() write("Press ^C to terminate") every f := [i:= 1] | factors(i := seq(2)) do {

  writes(i," : [")
  every writes(" ",!f|"]\n")
  }

end

link factors</lang>

Library: Icon Programming Library

factors.icn provides factors

Output:

1 : [ 1 ]
2 : [ 2 ]
3 : [ 3 ]
4 : [ 2 2 ]
5 : [ 5 ]
6 : [ 2 3 ]
7 : [ 7 ]
8 : [ 2 2 2 ]
9 : [ 3 3 ]
10 : [ 2 5 ]
11 : [ 11 ]
12 : [ 2 2 3 ]
13 : [ 13 ]
14 : [ 2 7 ]
15 : [ 3 5 ]
16 : [ 2 2 2 2 ]
...

J

Solution:Use J's factoring primitive, <lang j>q:</lang> Example (including formatting):<lang j> ('1 : 1',":&> ,"1 ': ',"1 ":@q:) 2+i.10 1 : 1 2 : 2 3 : 3 4 : 2 2 5 : 5 6 : 2 3 7 : 7 8 : 2 2 2 9 : 3 3 10: 2 5 11: 11</lang>

Java

Translation of: Visual Basic .NET

<lang java>public class CountingInFactors{

   public static void main(String[] args){
       for(int i = 1; i<= 10; i++){
           System.out.println(i + " = "+ countInFactors(i));
       }

       for(int i = 9991; i <= 10000; i++){
       	System.out.println(i + " = "+ countInFactors(i));
       }
   }

   private static String countInFactors(int n){
       if(n == 1) return "1";

       StringBuilder sb = new StringBuilder();

       n = checkFactor(2, n, sb);
       if(n == 1) return sb.toString();

       n = checkFactor(3, n, sb);
       if(n == 1) return sb.toString();

       for(int i = 5; i <= n; i+= 2){
           if(i % 3 == 0)continue;

           n = checkFactor(i, n, sb);
           if(n == 1)break;
       }

       return sb.toString();
   }

   private static int checkFactor(int mult, int n, StringBuilder sb){
       while(n % mult == 0 ){
           if(sb.length() > 0) sb.append(" x ");
           sb.append(mult);
           n /= mult;
       }
       return n;
   }

}</lang>

Output:

1 = 1
2 = 2
3 = 3
4 = 2 x 2
5 = 5
6 = 2 x 3
7 = 7
8 = 2 x 2 x 2
9 = 3 x 3
10 = 2 x 5
9991 = 97 x 103
9992 = 2 x 2 x 2 x 1249
9993 = 3 x 3331
9994 = 2 x 19 x 263
9995 = 5 x 1999
9996 = 2 x 2 x 3 x 7 x 7 x 17
9997 = 13 x 769
9998 = 2 x 4999
9999 = 3 x 3 x 11 x 101
10000 = 2 x 2 x 2 x 2 x 5 x 5 x 5 x 5

JavaScript

<lang javascript>for(i = 1; i <= 10; i++)

   console.log(i + " : " + factor(i).join(" x "));

function factor(n) {

   var factors = [];
   if (n == 1) return [1];
   for(p = 2; p <= n; ) {

if((n % p) == 0) { factors[factors.length] = p; n /= p; } else p++;

   }
   return factors;

}</lang>

Output:

1 : 1
2 : 2
3 : 3
4 : 2 x 2
5 : 5
6 : 2 x 3
7 : 7
8 : 2 x 2 x 2
9 : 3 x 3
10 : 2 x 5

Liberty BASIC

<lang lb> 'see Run BASIC solution for i = 1000 to 1016

 print i;" = "; factorial$(i)

next wait function factorial$(num)

if num = 1 then factorial$ = "1"
fct = 2
while fct <= num
if (num mod fct) = 0 then
  factorial$ = factorial$ ; x$ ; fct
  x$  = " x "
  num = num / fct
 else
  fct = fct + 1
end if
wend

end function </lang>

Output:

1000 = 2 x 2 x 2 x 5 x 5 x 5
1001 = 7 x 11 x 13
1002 = 2 x 3 x 167
1003 = 17 x 59
1004 = 2 x 2 x 251
1005 = 3 x 5 x 67
1006 = 2 x 503
1007 = 19 x 53
1008 = 2 x 2 x 2 x 2 x 3 x 3 x 7
1009 = 1009
1010 = 2 x 5 x 101
1011 = 3 x 337
1012 = 2 x 2 x 11 x 23
1013 = 1013
1014 = 2 x 3 x 13 x 13
1015 = 5 x 7 x 29
1016 = 2 x 2 x 2 x 127

Lua

<lang Lua>function factorize( n )

   if n == 1 then return {1} end

   local k = 2
   res = {}
   while n > 1 do

while n % k == 0 do res[#res+1] = k

	    n = n / k

end

	k = k + 1
   end
   return res

end

for i = 1, 22 do

   io.write( i, ":  " )
   fac = factorize( i )
   io.write( fac[1] )
   for j = 2, #fac do

io.write( " * ", fac[j] )

   end
   print ""

end</lang>

Mathematica

<lang Mathematica>n = 2; While[n < 100,

Print[Row[Riffle[Flatten[Map[Apply[ConstantArray, #] &, FactorInteger[n]]],"*"]]]; 
n++]</lang>

Objeck

<lang objeck> class CountingInFactors {

 function : Main(args : String[]) ~ Nil {
   for(i := 1; i <= 10; i += 1;){
   count := CountInFactors(i);
   ("{$i} = {$count}")->PrintLine();
 };

 for(i := 9991; i <= 10000; i += 1;){
   count := CountInFactors(i);
   ("{$i} = {$count}")->PrintLine();
   };
 }

 function : CountInFactors(n : Int) ~ String {
   if(n = 1) {
     return "1";
   };

   sb := "";
   n := CheckFactor(2, n, sb);
   if(n = 1) {
     return sb;
   };

   n := CheckFactor(3, n, sb);
   if(n = 1) {
     return sb;
   };

   for(i := 5; i <= n; i += 2;) {
     if(i % 3 <> 0) {
       n := CheckFactor(i, n, sb);
       if(n = 1) {
         break;
       };
     };
   };

   return sb;
 }

 function : CheckFactor(mult : Int, n : Int, sb : String) ~ Int {
   while(n % mult = 0 ) {
     if(sb->Size() > 0) {
       sb->Append(" x ");
     };
     sb->Append(mult);
     n /= mult;
   };

   return n;
 }

} </lang> Output:

1 = 1
2 = 2
3 = 3
4 = 2 x 2
5 = 5
6 = 2 x 3
7 = 7
8 = 2 x 2 x 2
9 = 3 x 3
10 = 2 x 5
9991 = 97 x 103
9992 = 2 x 2 x 2 x 1249
9993 = 3 x 3331
9994 = 2 x 19 x 263
9995 = 5 x 1999
9996 = 2 x 2 x 3 x 7 x 7 x 17
9997 = 13 x 769
9998 = 2 x 4999
9999 = 3 x 3 x 11 x 101
10000 = 2 x 2 x 2 x 2 x 5 x 5 x 5 x 5

OCaml

<lang ocaml>open Big_int

let prime_decomposition x =

 let rec inner c p =
   if lt_big_int p (square_big_int c) then
     [p]
   else if eq_big_int (mod_big_int p c) zero_big_int then
     c :: inner c (div_big_int p c)
   else
     inner (succ_big_int c) p
 in
 inner (succ_big_int (succ_big_int zero_big_int)) x

let () =

 let rec aux v =
   let ps = prime_decomposition v in
   print_string (string_of_big_int v);
   print_string " = ";
   print_endline (String.concat " x " (List.map string_of_big_int ps));
   aux (succ_big_int v)
 in
 aux unit_big_int</lang>

Execution:

$ ocamlopt -o count.opt nums.cmxa count.ml
$ ./count.opt
1 = 1
2 = 2
3 = 3
4 = 2 x 2
5 = 5
6 = 2 x 3
7 = 7
8 = 2 x 2 x 2
...
6351 = 3 x 29 x 73
6352 = 2 x 2 x 2 x 2 x 397
6353 = 6353
6354 = 2 x 3 x 3 x 353
6355 = 5 x 31 x 41
6356 = 2 x 2 x 7 x 227
6357 = 3 x 13 x 163
6358 = 2 x 11 x 17 x 17
6359 = 6359
^C

Octave

Octave's factor function returns an array: <lang octave>for (n = 1:20)

   printf ("%i: ", n)
   printf ("%i ", factor (n))
   printf ("\n")

endfor</lang>

Output:

1: 1
2: 2
3: 3
4: 2 2
5: 5
6: 2 3
7: 7
8: 2 2 2
9: 3 3
10: 2 5
11: 11
12: 2 2 3
13: 13
14: 2 7
15: 3 5
16: 2 2 2 2
17: 17
18: 2 3 3
19: 19
20: 2 2 5

PARI/GP

<lang parigp>fnice(n)={ my(f,s="",s1); if (n < 2, return(n)); f = factor(n); s = Str(s, f[1,1]); if (f[1, 2] != 1, s=Str(s, "^", f[1,2])); for(i=2,#f[,1], s1 = Str(" * ", f[i, 1]); if (f[i, 2] != 1, s1 = Str(s1, "^", f[i, 2])); s = Str(s, s1) ); s }; n=0;while(n++, print(fnice(n)))</lang>

Pascal

Works with: Free_Pascal

<lang pascal>program CountInFactors(output);

type

 TdynArray = array of integer;

function factorize(number: integer): TdynArray;

 var
   k: integer;
 begin
   if number = 1 then
   begin
     setlength(factorize, 1);
     factorize[0] := 1
   end
   else
   begin
     k := 2;
     while number > 1 do
     begin

while number mod k = 0 do begin setlength(factorize, length(factorize) + 1); factorize[high(factorize)] := k; number := number div k; end; inc(k);

     end;
   end
 end;

var

 i, j: integer;
 fac: TdynArray;

begin

 for i := 1 to 22 do
 begin
   write(i, ':  ' );
   fac := factorize(i);
   write(fac[0]);
   for j := 1 to high(fac) do
     write(' * ', fac[j]);
   writeln;
 end;

end.</lang>

Output:

1:  1
2:  2
3:  3
4:  2 * 2
5:  5
6:  2 * 3
7:  7
8:  2 * 2 * 2
9:  3 * 3
10:  2 * 5
11:  11
12:  2 * 2 * 3
13:  13
14:  2 * 7
15:  3 * 5
16:  2 * 2 * 2 * 2
17:  17
18:  2 * 3 * 3
19:  19
20:  2 * 2 * 5
21:  3 * 7
22:  2 * 11

Perl

<lang perl>use utf8; sub factors { my $n = shift; my $p = 2; my @out;

while ($n >= $p * $p) { while ($n % $p == 0) { push @out, $p; $n /= $p; } $p = next_prime($p); } push @out, $n if $n > 1 || !@out; @out; }

sub next_prime { my $p = shift; do { $p = $p == 2 ? 3 : $p + 2 } until is_prime($p); $p; }

sub is_prime { factors(shift) == 1 }

print "$_ = ", join(" × ", factors($_)), "\n" for (1 .. 1000);</lang>

Perl 6

<lang perl6># Define a lazy list of primes.

Uses the ... sequence operator with a lambda that calculates
the next available prime by using some of the existing list
as test divisors, so we rarely divide by anything that isn't
known to be a prime already. This is quite fast.

my @primes := 2, 3, 5, -> $p { ($p+2, $p+4 ... &prime)[*-1] } ... *; my @isprime = False,False; # 0 and 1 are not prime by definition sub prime($i) { @isprime[$i] //= $i %% none @primes ...^ * > sqrt $i }

Finds the factors of the given argument.

multi factors(1) { 1 } multi factors(Int $remainder is copy) {

 gather for @primes -> $factor {

   # if remainder < factor², we're done
   if $factor * $factor > $remainder {
     take $remainder if $remainder > 1;
     last;
   }

   # How many times can we divide by this prime?
   while $remainder %% $factor {
       take $factor;
       last if ($remainder div= $factor) === 1;
   }
 }

}

An infinite loop, from 1 incrementing upward.
calls factor() with each of 1, 2, 3, etc., receives an
array containing that number's factors, and then
formats and displays them.

say "$_: ", factors($_).join(" × ") for 1..*;</lang> The first twenty numbers:

1: 1
2: 2
3: 3
4: 2 × 2
5: 5
6: 2 × 3
7: 7
8: 2 × 2 × 2
9: 3 × 3
10: 2 × 5
11: 11
12: 2 × 2 × 3
13: 13
14: 2 × 7
15: 3 × 5
16: 2 × 2 × 2 × 2
17: 17
18: 2 × 3 × 3
19: 19
20: 2 × 2 × 5

Here we use a multi declaration with a constant parameter to match the degenerate case. We use copy parameters when we wish to reuse the formal parameter as a mutable variable within the function. (Parameters default to readonly in Perl 6.) Note the use of gather/take as the final statement in the function, which is a common Perl 6 idiom to set up a coroutine within a function to return a lazy list on demand.

Note also the '×' above is not ASCII 'x', but U+00D7 MULTIPLICATION SIGN. Perl 6 does Unicode natively.

PicoLisp

This is the 'factor' function from Prime decomposition#PicoLisp. <lang PicoLisp>(de factor (N)

  (make
     (let (D 2  L (1 2 2 . (4 2 4 2 4 6 2 6 .))  M (sqrt N))
        (while (>= M D)
           (if (=0 (% N D))
              (setq M (sqrt (setq N (/ N (link D)))))
              (inc 'D (pop 'L)) ) )
        (link N) ) ) )

(for N 20

  (prinl N ": " (glue " * " (factor N))) )</lang>

Output:

1: 1
2: 2
3: 3
4: 2 * 2
5: 5
6: 2 * 3
7: 7
8: 2 * 2 * 2
9: 3 * 3
10: 2 * 5
11: 11
12: 2 * 2 * 3
13: 13
14: 2 * 7
15: 3 * 5
16: 2 * 2 * 2 * 2
17: 17
18: 2 * 3 * 3
19: 19
20: 2 * 2 * 5

PL/I

<lang PL/I> cnt: procedure options (main); declare (i, k, n) fixed binary; declare first bit (1) aligned;

  do n = 1 to 40;
     put skip list (n || ' =');
     k = n; first = '1'b;

repeat:

     do i = 2 to k-1;

if mod(k, i) = 0 then do; k = k/i;

                               if ^first then put edit (' x ')(A);
                               first = '0'b;
                               put edit (trim(i)) (A);

go to repeat; end;

end;

       if ^first then put edit (' x ')(A);
       if n = 1 then i = 1;
       put edit (trim(i)) (A);
  end;

end cnt; </lang> Results:

        1 = 1
        2 = 2
        3 = 3
        4 = 2 x 2
        5 = 5
        6 = 2 x 3
        7 = 7
        8 = 2 x 2 x 2
        9 = 3 x 3
       10 = 2 x 5
       11 = 11
       12 = 2 x 2 x 3
       13 = 13
       14 = 2 x 7
       15 = 3 x 5
       16 = 2 x 2 x 2 x 2
       17 = 17
       18 = 2 x 3 x 3
       19 = 19
       20 = 2 x 2 x 5
       21 = 3 x 7
       22 = 2 x 11
       23 = 23
       24 = 2 x 2 x 2 x 3
       25 = 5 x 5
       26 = 2 x 13
       27 = 3 x 3 x 3
       28 = 2 x 2 x 7
       29 = 29
       30 = 2 x 3 x 5
       31 = 31
       32 = 2 x 2 x 2 x 2 x 2
       33 = 3 x 11
       34 = 2 x 17
       35 = 5 x 7
       36 = 2 x 2 x 3 x 3
       37 = 37
       38 = 2 x 19
       39 = 3 x 13
       40 = 2 x 2 x 2 x 5

PureBasic

<lang PureBasic>Procedure Factorize(Number, List Factors())

 Protected I = 3, Max
 ClearList(Factors())
 While Number % 2 = 0
   AddElement(Factors())
   Factors() = 2
   Number / 2
 Wend
 Max = Number
 While I <= Max And Number > 1
   While Number % I = 0
     AddElement(Factors())
     Factors() = I
     Number / I
   Wend
   I + 2
 Wend

EndProcedure

If OpenConsole()

 NewList n()
 For a=1 To 20
   text$=RSet(Str(a),2)+"= "
   Factorize(a,n())
   If ListSize(n())
     ResetList(n())
     While NextElement(n())
       text$ + Str(n())
       If ListSize(n())-ListIndex(n())>1
         text$ + "*"
       EndIf
     Wend
   Else
     text$+Str(a) ; To handle the '1', which is not really a prime...
   EndIf
   PrintN(text$)
 Next a

EndIf</lang>

Output:

 1= 1
 2= 2
 3= 3
 4= 2*2
 5= 5
 6= 2*3
 7= 7
 8= 2*2*2
 9= 3*3
10= 2*5
11= 11
12= 2*2*3
13= 13
14= 2*7
15= 3*5
16= 2*2*2*2
17= 17
18= 2*3*3
19= 19
20= 2*2*5

Python

This uses the functools.lru_cache standard library module to cache intermediate results. <lang python>from functools import lru_cache

primes = [2, 3, 5, 7, 11, 13, 17] # Will be extended

@lru_cache(maxsize=2000) def pfactor(n):

   if n == 1:
       return [1]
   n2 = n // 2 + 1
   for p in primes:
       if p <= n2:
           d, m = divmod(n, p)
           if m == 0:
               if d > 1:
                   return [p] + pfactor(d)
               else:
                   return [p]
       else:
           if n > primes[-1]:
               primes.append(n)
           return [n]

if __name__ == '__main__':

   mx = 5000
   for n in range(1, mx + 1):
       factors = pfactor(n)
       if n <= 10 or n >= mx - 20:
           print( '%4i %5s %s' % (n,
                                   if factors != [n] else 'prime',
                                  'x'.join(str(i) for i in factors)) )
       if n == 11:
           print('...')
           
   print('\nNumber of primes gathered up to', n, 'is', len(primes))
   print(pfactor.cache_info())</lang>

Output:

   1 prime 1
   2 prime 2
   3 prime 3
   4       2x2
   5 prime 5
   6       2x3
   7 prime 7
   8       2x2x2
   9       3x3
  10       2x5
...
4980       2x2x3x5x83
4981       17x293
4982       2x47x53
4983       3x11x151
4984       2x2x2x7x89
4985       5x997
4986       2x3x3x277
4987 prime 4987
4988       2x2x29x43
4989       3x1663
4990       2x5x499
4991       7x23x31
4992       2x2x2x2x2x2x2x3x13
4993 prime 4993
4994       2x11x227
4995       3x3x3x5x37
4996       2x2x1249
4997       19x263
4998       2x3x7x7x17
4999 prime 4999
5000       2x2x2x5x5x5x5

Number of primes gathered up to 5000 is 669
CacheInfo(hits=3935, misses=7930, maxsize=2000, currsize=2000)

Racket

lang racket

(require math)

(define (~ f)

 (match f
   [(list p 1) (~a p)]
   [(list p n) (~a p "^" n)]))

(for ([x (in-range 2 20)])

 (display (~a x " = "))
 (for-each display (add-between (map ~ (factorize x)) " * "))
 (newline))

</lang> Output:

2 = 2
3 = 3
4 = 2^2
5 = 5
6 = 2 * 3
7 = 7
8 = 2^3
9 = 3^2
10 = 2 * 5
11 = 11
12 = 2^2 * 3
13 = 13
14 = 2 * 7
15 = 3 * 5
16 = 2^4
17 = 17
18 = 2 * 3^2
19 = 19

REXX

It couldn't be determined if the x (for multiplication) was a strict requirement or
whether there're blanks surrounding the x (blanks were assumed for this example for readability).
There's commented code that shows how to not include blanks around the x [see comment about BLANKS=0 (6th statement)].

Also, as per the task's requirements, the prime factors of 1 (unity) will be listed as 1,
even though, strictly speaking, it should be null. <lang rexx>/*REXX program finds and lists the prime factors of positive integer(s).*/ numeric digits 12 /*bump precision of the numbers. */ parse arg low high . /*get the argument(s) from the CL*/ if high== then high=low /*No HIGH? Then make one up. */ w=length(high) /*get max width for pretty tell. */ blanks=1 /*allow spaces around the "x". */

        do n=low  to high             /*process single number | a range*/
        say right(n,w) '=' space(factr(n),blanks) /*display N & factors*/
        end   /*n*/                   /*if BLANKS=0, no spaces around X*/

exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────FACTR subroutine────────────────────*/ factr: procedure; parse arg x 1 z /*defines X and Z from the arg.*/ if x <1 then return /*Invalid number? Return null. */ if x==1 then return 1 /*handle special case for unity. */ Xtimes= '∙' /*use round bullet for "times". */ Xtimes= 'x' /*character used for "times" (x).*/ list= /*nullify the list (to empty). */

 do j=2 to 5; if j\==4  then call .buildF; end  /*fast builds for list.*/
 j=5                                  /*start were we left off  (five).*/
      do y=0  by 2;     j=j+2+y//4    /*insure it's not divisible by 3.*/
      if right(j,1)==5  then iterate  /*fast check  for divisible by 5.*/
      if   j>z          then leave    /*number reduced to a small 'un? */
      if j*j>x          then leave    /*are we higher than the √ of X ?*/
      call .buildF                    /*add a prime factor to list (J).*/
      end    /*y*/

if z==1 then z= /*if residual is = 1, nullify it.*/ return strip(strip(list Xtimes z),,Xtimes) /*elide any leading "x". */ /*──────────────────────────────────.BUILDF subroutine──────────────────*/ .buildF: do while z//j==0 /*keep dividing until it hurts. */

          list=list Xtimes j          /*add number to the list  (J).   */
          z=z%j                       /*do an integer divide.          */
          end   /*while*/

return</lang> output when using the input of: 1 30

 1 = 1
 2 = 2
 3 = 3
 4 = 2 x 2
 5 = 5
 6 = 2 x 3
 7 = 7
 8 = 2 x 2 x 2
 9 = 3 x 3
10 = 2 x 5
11 = 11
12 = 2 x 2 x 3
13 = 13
14 = 2 x 7
15 = 3 x 5
16 = 2 x 2 x 2 x 2
17 = 17
18 = 2 x 3 x 3
19 = 19
20 = 2 x 2 x 5
21 = 3 x 7
22 = 2 x 11
23 = 23
24 = 2 x 2 x 2 x 3
25 = 5 x 5
26 = 2 x 13
27 = 3 x 3 x 3
28 = 2 x 2 x 7
29 = 29
30 = 2 x 3 x 5

Ruby

Starting with Ruby 1.9, 'prime' is part of the standard library and provides Integer#prime_division. <lang ruby>require 'optparse' require 'prime'

maximum = 10 OptionParser.new do |o|

 o.banner = "Usage: #{File.basename $0} [-m MAXIMUM]"
 o.on("-m MAXIMUM", Integer,
      "Count up to MAXIMUM [#{maximum}]") { |m| maximum = m }
 o.parse! rescue ($stderr.puts $!, o; exit 1)
 ($stderr.puts o; exit 1) unless ARGV.size == 0

end

1 has no prime factors

puts "1 is 1" unless maximum < 1

2.upto(maximum) do |i|

 # i is 504 => i.prime_division is [[2, 3], [3, 2], [7, 1]]
 f = i.prime_division.map! do |factor, exponent|
   # convert [2, 3] to "2 x 2 x 2"
   ([factor] * exponent).join " x "
 end.join " x "
 puts "#{i} is #{f}"

end</lang>

Example:

$ ruby prime-count.rb -h
Usage: prime-count.rb [-m MAXIMUM]
    -m MAXIMUM                       Count up to MAXIMUM [10]
$ ruby prime-count.rb -m 10000 | sed -e '11,9990d' 
1 is 1
2 is 2
3 is 3
4 is 2 x 2
5 is 5
6 is 2 x 3
7 is 7
8 is 2 x 2 x 2
9 is 3 x 3
10 is 2 x 5
9991 is 97 x 103
9992 is 2 x 2 x 2 x 1249
9993 is 3 x 3331
9994 is 2 x 19 x 263
9995 is 5 x 1999
9996 is 2 x 2 x 3 x 7 x 7 x 17
9997 is 13 x 769
9998 is 2 x 4999
9999 is 3 x 3 x 11 x 101
10000 is 2 x 2 x 2 x 2 x 5 x 5 x 5 x 5

Run BASIC

<lang runbasic>for i = 1000 to 1016

 print i;" = "; factorial$(i)

next wait function factorial$(num)

if num = 1 then factorial$ = "1"
fct = 2
while fct <= num
if (num mod fct) = 0 then
  factorial$ = factorial$ ; x$ ; fct
  x$  = " x "
  num = num / fct
 else
  fct = fct + 1
end if
wend

end function</lang>

Output:

1000 = 2 x 2 x 2 x 5 x 5 x 5
1001 = 7 x 11 x 13
1002 = 2 x 3 x 167
1003 = 17 x 59
1004 = 2 x 2 x 251
1005 = 3 x 5 x 67
1006 = 2 x 503
1007 = 19 x 53
1008 = 2 x 2 x 2 x 2 x 3 x 3 x 7
1009 = 1009
1010 = 2 x 5 x 101
1011 = 3 x 337
1012 = 2 x 2 x 11 x 23
1013 = 1013
1014 = 2 x 3 x 13 x 13
1015 = 5 x 7 x 29
1016 = 2 x 2 x 2 x 127

Scheme

<lang lisp>(define (factors n)

 (let facs ((l '()) (d 2) (x n))
   (cond ((= x 1) (if (null? l) '(1) l))

((< x (* d d)) (cons x l)) (else (if (= 0 (modulo x d)) (facs (cons d l) d (/ x d)) (facs l (+ 1 d) x))))))

(define (show l)

 (display (car l))
 (if (not (null? (cdr l)))
   (begin
     (display " × ")
     (show (cdr l)))
   (display "\n")))

(do ((i 1 (+ i 1))) (#f)

 (display i)
 (display " = ")
 (show (reverse (factors i))))</lang>

Output:

1 = 1
2 = 2
3 = 3
4 = 2 × 2
5 = 5
6 = 2 × 3
7 = 7
8 = 2 × 2 × 2
9 = 3 × 3
10 = 2 × 5
11 = 11
12 = 2 × 2 × 3
...

Seed7

<lang seed7>$ include "seed7_05.s7i";

const proc: writePrimeFactors (in var integer: number) is func

 local
   var boolean: laterElement is FALSE;
   var integer: checker is 2;
 begin
   while checker * checker <= number do
     if number rem checker = 0 then
       if laterElement then
         write(" * ");
       end if;
       laterElement := TRUE;
       write(checker);
       number := number div checker;
     else
       incr(checker);
     end if;
   end while;
   if number <> 1 then
     if laterElement then
       write(" * ");
     end if;
     laterElement := TRUE;
     write(number);
   end if;
 end func;

const proc: main is func

 local
   var integer: number is 0;
 begin
   writeln("1: 1");
   for number range 2 to 2147483647 do
     write(number <& ": ");
     writePrimeFactors(number);
     writeln;
   end for;
 end func;</lang>

Output:

1: 1
2: 2
3: 3
4: 2 * 2
5: 5
6: 2 * 3
7: 7
8: 2 * 2 * 2
9: 3 * 3
10: 2 * 5
11: 11
12: 2 * 2 * 3
13: 13
14: 2 * 7
15: 3 * 5
. . .

Tcl

This factorization code is based on the same engine that is used in the parallel computation task. <lang tcl>package require Tcl 8.5

namespace eval prime {

   variable primes [list 2 3 5 7 11]
   proc restart {} {

variable index -1 variable primes variable current [lindex $primes end]

   proc get_next_prime {} {

variable primes variable index if {$index < [llength $primes]-1} { return [lindex $primes [incr index]] } variable current while 1 { incr current 2 set p 1 foreach prime $primes { if {$current % $prime} {} else { set p 0 break } } if {$p} { return [lindex [lappend primes $current] [incr index]] } }

   proc factors {num} {

restart set factors [dict create] for {set i [get_next_prime]} {$i <= $num} {} { if {$num % $i == 0} { dict incr factors $i set num [expr {$num / $i}] continue } elseif {$i*$i > $num} { dict incr factors $num break } else { set i [get_next_prime] } } return $factors

   # Produce the factors in rendered form
   proc factors.rendered {num} {

set factorDict [factors $num] if {[dict size $factorDict] == 0} { return 1 } dict for {factor times} $factorDict { lappend v {*}[lrepeat $times $factor] } return [join $v "*"]

}</lang> Demonstration code: <lang tcl>set max 20 for {set i 1} {$i <= $max} {incr i} {

   puts [format "%*d = %s" [string length $max] $i [prime::factors.rendered $i]]

}</lang>

Visual Basic .NET

<lang vbnet>Module CountingInFactors

   Sub Main()
       For i As Integer = 1 To 10
           Console.WriteLine("{0} = {1}", i, CountingInFactors(i))
       Next

       For i As Integer = 9991 To 10000
           Console.WriteLine("{0} = {1}", i, CountingInFactors(i))
       Next
   End Sub

   Private Function CountingInFactors(ByVal n As Integer) As String
       If n = 1 Then Return "1"

       Dim sb As New Text.StringBuilder()

       CheckFactor(2, n, sb)
       If n = 1 Then Return sb.ToString()

       CheckFactor(3, n, sb)
       If n = 1 Then Return sb.ToString()

       For i As Integer = 5 To n Step 2
           If i Mod 3 = 0 Then Continue For

           CheckFactor(i, n, sb)
           If n = 1 Then Exit For
       Next

       Return sb.ToString()
   End Function

   Private Sub CheckFactor(ByVal mult As Integer, ByRef n As Integer, ByRef sb As Text.StringBuilder)
       Do While n Mod mult = 0
           If sb.Length > 0 Then sb.Append(" x ")
           sb.Append(mult)
           n = n / mult
       Loop
   End Sub

End Module</lang>

Output:

1 = 1
2 = 2
3 = 3
4 = 2 x 2
5 = 5
6 = 2 x 3
7 = 7
8 = 2 x 2 x 2
9 = 3 x 3
10 = 2 x 5
9991 = 97 x 103
9992 = 2 x 2 x 2 x 1249
9993 = 3 x 3331
9994 = 2 x 19 x 263
9995 = 5 x 1999
9996 = 2 x 2 x 3 x 7 x 7 x 17
9997 = 13 x 769
9998 = 2 x 4999
9999 = 3 x 3 x 11 x 101
10000 = 2 x 2 x 2 x 2 x 5 x 5 x 5 x 5

XPL0

<lang XPL0>include c:\cxpl\codes; int N0, N, F; [N0:= 1; repeat IntOut(0, N0); Text(0, " = ");

       F:= 2;  N:= N0;
       repeat  if rem(N/F) = 0 then
                       [if N # N0 then Text(0, " * ");
                       IntOut(0, F);
                       N:= N/F;
                       ]
               else F:= F+1;
       until F>N;
       if N0=1 then IntOut(0, 1);      \1 = 1
       CrLf(0);
       N0:= N0+1;

until KeyHit; ]</lang>

Example output:

1 = 1
2 = 2
3 = 3
4 = 2 * 2
5 = 5
6 = 2 * 3
7 = 7
8 = 2 * 2 * 2
9 = 3 * 3
10 = 2 * 5
11 = 11
12 = 2 * 2 * 3
13 = 13
14 = 2 * 7
15 = 3 * 5
16 = 2 * 2 * 2 * 2
17 = 17
18 = 2 * 3 * 3
. . .
57086 = 2 * 17 * 23 * 73
57087 = 3 * 3 * 6343
57088 = 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 223
57089 = 57089
57090 = 2 * 3 * 5 * 11 * 173
57091 = 37 * 1543
57092 = 2 * 2 * 7 * 2039
57093 = 3 * 19031
57094 = 2 * 28547
57095 = 5 * 19 * 601
57096 = 2 * 2 * 2 * 3 * 3 * 13 * 61
57097 = 57097