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, may be shown as itself.
For examle, is prime, so it would be shown as itself. is not prime; it would be shown as . Likewise, 2144 is not prime; it would be shown as .
c.f. Prime decomposition
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
<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 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>
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>
- 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
<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
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:
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
<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 never divide by anything that isn't
- 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;
} ... *;
- 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
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)
REXX
It couldn't be determined if the x (for times) was a strict requirement or
whether there're blanks surrounding the x (blanks were assumed for this example).
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 to find/list the prime factors of positive integer(s). */
numeric digits 100 /*bump up precision of the numbers. */ parse arg low high . /*get the argument(s). */ if high== then high=low /*no HIGH? Then make one up. */ w=length(high) /*get maximum width for pretty tell.*/
do n=low to high /*process single number or a range. */ say right(n,w) '=' factr(n) end
exit
/*─────────────────────────────────FACTR subroutine────────────────────*/ factr: procedure; parse arg x 1 z /*defines X and Z to the argument. */ if x <1 then return /*invalid number? Then return null.*/ if x==1 then return 1 /*special case for unity. */ times='x' /*character used for "times" (x). */ list=
do j=2 to 5; if j\==4 then call buildF; end /*fast builds for list.*/
j=5 /*start were we left off (J=5). */
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 number? */ if j*j>x then leave /*are we higher than the sqrt of X ?*/ call buildF /*add a prime factor to the list (J)*/ end
if z==1 then z= /*if residual is unity, nullify it. */ z=strip(strip(list z),,times) /*get rid of leading X (maybe)*/ return strip(z) /*return the list, append residual. */
/*─────────────────────────────────BUILDF subroutine───────────────────*/ buildF: do forever /*keep dividing until it hurts. */
if z//j\==0 then return /*can't divide any more? */
list=list times j /*add number to the list (J). */
z=z%j /*do an integer divide. */
end
</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 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 7 22 = 2 11 23 = 23 24 = 2 x 2 x 2 x 3 25 = 5 x 5 26 = 2 13 27 = 3 x 3 x 3 28 = 2 x 2 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
- Programming Tasks
- Solutions by Programming Task
- Ada
- AutoHotkey
- BBC BASIC
- C
- C sharp
- CoffeeScript
- Common Lisp
- D
- Uiprimes
- DWScript
- Euphoria
- Forth
- Go
- Groovy
- Haskell
- Icon
- Unicon
- Icon Programming Library
- J
- Java
- JavaScript
- Lua
- Mathematica
- OCaml
- Octave
- PARI/GP
- Pascal
- Perl
- Perl 6
- PicoLisp
- PureBasic
- Python
- REXX
- Ruby
- Run BASIC
- Scheme
- Seed7
- Tcl
- Visual Basic .NET
- XPL0