Count in factors: Difference between revisions
(→Tcl: Added implementation) |
m (→{{header|D}}: Move library information to front) |
||
Line 5: | Line 5: | ||
c.f. [[Prime decomposition]] |
c.f. [[Prime decomposition]] |
||
=={{header|D}}== |
=={{header|D}}== |
||
⚫ | |||
<lang d>import std.stdio, std.math, std.conv, std.algorithm, std.array, std.string ; |
<lang d>import std.stdio, std.math, std.conv, std.algorithm, std.array, std.string ; |
||
import xt.uiprimes ; |
import xt.uiprimes ; |
||
Line 37: | Line 38: | ||
writefln("%2d = %s", i, productStr(factorize(i))) ; |
writefln("%2d = %s", i, productStr(factorize(i))) ; |
||
}</lang> |
}</lang> |
||
⚫ | |||
=={{header|J}}== |
=={{header|J}}== |
||
Revision as of 20:58, 24 December 2010
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
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>
Perl 6
The first two multi prime lines are adapted from Perl 6's entry at Primality by Trial Division. <lang perl6># Multi function to test a number for primality.
- Which function body is called depends on which one's
- criteria most-specifically matches the given argument
- values.
multi prime(Int $n where ( $n <= 1)) { False } multi prime(Int $n --> Bool) {
$n %% none 2, 3, *+2 ...^ * > sqrt $n;
}
- Returns the next prime greater than the value given.
multi next_prime(2) { 3 } multi next_prime(Int $check is copy --> Int) {
repeat until prime($check) { $check += 2 } return $check;
}
- binding to an array memoizes primes list
my @primes := 2, { next_prime($^a) } ... *;
- Finds the factors of the given argument.
multi factors(1) { 1 } multi factors(Int $remainder is copy) {
gather for @primes -> $factor { # How many times can we divide by this prime? while $remainder %% $factor { take $factor; last if ($remainder /= $factor) == 1; } last if $remainder == 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(" x ") for 1..*;</lang>
The first twenty numbers:
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
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.
The second last is a workaround since rakudo does not yet support loop exit via loop labels.
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
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>