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
D
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>
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
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+2715, MULTIPLICATION X. 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
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 -? invalid option: -? Usage: prime-count.rb [-m MAXIMUM] -m MAXIMUM Count up to MAXIMUM [10] $ ruby prime-count.rb -m 10000 | (head -n 10; tail -n 10) 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
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