Count in factors: Difference between revisions

Content added Content deleted

Inline

Revision as of 03:23, 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, $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

D

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

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

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 prime(Int $n where ( $n <= 1)) { False } multi prime(Int $n --> Bool) {

   $n %% none 2, 3, *+2 ...^ * > sqrt $n;

}

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) } ... *;

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

}

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

Use the 'factor' function from Prime decomposition#PicoLisp. <lang PicoLisp>(for N 20

  (prinl N ": " (or (glue " * " (factor N)) 1)) )</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

@@ Line 57: / Line 57: @@
 The first two <tt>multi prime</tt> lines are adapted from Perl 6's entry at [[Primality by Trial Division]].
-<lang perl6>multi prime (Int $n --> Bool) {
+<lang perl6>multi prime(Int $n where ( $n <= 1)) { False }
+multi prime(Int $n --> Bool) {
     $n %% none 2, 3, *+2 ...^ * > sqrt $n;
 }
-multi prime (Int $n where ( $n <= 1)) {
+multi next_prime(2) { 3 }
+multi next_prime(Int $check is copy --> Int) {
-    False;
+    repeat until prime($check) { $check += 2 }
-}
-sub next_prime(Int $start --> Int) {
-    my $check = $start + 1;
-    if  $check %% 2 and $check > 2  { ++$check }
-    until prime($check) { $check += 2 }
     return $check;
 }
+# binding to an array memoizes primes list
-my @primes := 2, -> $a { next_prime($a) } ... *;
+my @primes := 2, { next_prime($^a) } ... *;
-multi factor(Int $inFactor where ( $inFactor == 1 ) )
+multi factors(1) { 1 }
+multi factors(Int $remainder is copy) {
-{
+  gather for @primes -> $factor {
-  (1);
+    # How many times can we divide by this prime?
-}
+    while $remainder %% $factor {
+        take $factor;
-multi factor(Int $toFactor)
+        last if ($remainder /= $factor) == 1;
-{
+    }
-  my $currentRemainder = $toFactor;
+    last if $remainder == 1;
-  my @factors;
-  # Iterate through our primes until we find a prime number that's a factor of $currentRemainder;
-  until 1 == $currentRemainder {
-    my $primeIndex = 0;
-    # Find a factor of our current remainder.
-    until $currentRemainder %% @primes[$primeIndex] { ++$primeIndex }
-    # We found our next factor.
-    @factors.push(@primes[$primeIndex]);
-    # Some bookkeeping.
-    $currentRemainder /= @primes[$primeIndex];
   }
-  @factors;
 }
+say "$_: ", factors($_).join(" x ") for 1..*;</lang>
-for 1..* {
-  print "$_: ";
-  say factor($_).join(" x ");
-}</lang>
 The first twenty numbers:
@@ Line 131: / Line 107: @@
 : 19
 : 2 x 2 x 5</pre>
+Here we use a <tt>multi</tt> declaration with a constant parameter to match the degenerate case.  We use <tt>copy</tt> parameters when we wish to reuse the formal parameter as a mutable variable within the function. (Parameters default to readonly in Perl&nbsp;6.) Note the use of <tt>gather</tt>/<tt>take</tt> as the final statement in the function, which is a common Perl&nbsp;6 idiom to set up a coroutine within a function to return a lazy list on demand.
+The second <tt>last</tt> is a workaround since rakudo does not yet support loop exit via loop labels.
 =={{header|PicoLisp}}==