Count in factors

Count in factors
You are encouraged to solve this task according to the task description, using any language you may know.

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

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>

1. 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:<lang>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 . . .</lang>

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

Translation of: Ada

<lang d>import std.stdio, std.string, std.algorithm, std.array, std.conv;

int[] factorize(int n) 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() {

   foreach (i; 1 .. 22)
       writeln(i, ": ", join(array(map!text(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

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 = n / p ;
           }
   }
   if(n > 1)
       res ~= [n] ;
   return res ;

}

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

   return array(map!q{to!string(a)}(nums)).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

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
...

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 13 = 13 . . .

• 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 2155 = 5 * 431 . . .

• Main> mapM_ (putStrLn . showFactors ) [1231231232155..]

1231231232155 = 5 * 246246246431 1231231232156 = 2 * 2 * 37 * 113 * 73620619 1231231232157 = 3 * 11287 * 36361337 1231231232158 = 2 * 2039 * 4643 * 65027 1231231232159 = 1231231232159 1231231232160 = 2 * 2 * 2 * 2 * 2 * 3 * 3 * 5 * 61 * 71 * 197419 1231231232161 = 7 * 175890176023 1231231232162 = 2 * 19 * 32400821899 1231231232163 = 3 * 410410410721 1231231232164 = 2 * 2 * 307807808041 1231231232165 = 5 * 11 * 29 * 47 * 16424081 . . .</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: <lang> 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 </lang>

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>

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

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>

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.

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

my @primes := 2, 3, -> $n is copy {

   repeat { $n += 2 } until $n %% none do for @primes -> $p {
       last if $p > sqrt($n);
       $p;
   }
   $n;

} ... *;

1. 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;
   }
 }

}

1. An infinite loop, from 1 incrementing upward.
2. calls factor() with each of 1, 2, 3, etc., receives an
3. array containing that number's factors, and then
4. 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

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>

 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>

Sample 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)

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. 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

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

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