Count in factors

Count in factors is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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 --> Bool) {

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

}

multi prime (Int $n where ( $n <= 1)) {

   False;

}

sub next_prime(Int $start --> Int) {

   my $check = $start + 1;
   if  $check %% 2 and $check > 2  { ++$check }

   until prime($check) { $check += 2 }

   return $check;

}

my @primes := 2, -> $a { next_prime($a) } ... *;

multi factor(Int $inFactor where ( $inFactor == 1 ) ) {

 (1);

}

multi factor(Int $toFactor) {

 my $currentRemainder = $toFactor;

 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;

}

for 1..* {

 print "$_: ";
 say factor($_).join(" x ");

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

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