Count in factors: Difference between revisions

From Rosetta Code
Content added Content deleted
(→‎{{header|Ruby}}: Remove {{libheader}} calls. Both 'optparse' and 'prime' are from the standard library, and this is the only page in the otherwise nonexistant 'optparse' and 'prime' categories.)
m (→‎{{header|Ruby}}: optparse provides -h option, so use -h instead of -?.)
Line 722: Line 722:
end</lang>
end</lang>


Example: <pre>$ ruby prime-count.rb -?
Example: <pre>$ ruby prime-count.rb -h
invalid option: -?
Usage: prime-count.rb [-m MAXIMUM]
Usage: prime-count.rb [-m MAXIMUM]
-m MAXIMUM Count up to MAXIMUM [10]
-m MAXIMUM Count up to MAXIMUM [10]

Revision as of 16:30, 22 August 2011

Task
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

Category:Prime_Numbers

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

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>

  1. 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:<lang>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 . . .</lang>

D

Translation of: Ada

<lang d>import std.stdio, std.string, std.algorithm, std.array, std.conv;

int[] factorize(int n) 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() { 

   foreach (i; 1 .. 22)
       writeln(i, ": ", join(array(map!text(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

Alternative version

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

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

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

Haskell

<lang Haskell> primes = [2] ++ filter is_prime [3..]

is_prime num = foldl (\acc x -> acc && (num `mod` x /= 0)) True $ takeWhile (<= floor ((fromIntegral num)/2)) primes

-- spf = smallest prime factor spf num = head.take 1 $ dropWhile (\x -> (num `mod` x) /= 0) primes

factors num 

   |is_prime num = [num]
   |otherwise = (spf num) : factors (floor ((fromIntegral num) / (fromIntegral (spf num))))

map factors [1..] </lang>

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>

Library: Icon Programming Library

factors.icn provides factors

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

Translation of: Visual Basic .NET

<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

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>

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.

  1. Uses the ... sequence operator with a lambda that calculates
  2. the next available prime by using some of the existing list
  3. as test divisors, so we never divide by anything that isn't
  4. 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;

} ... *;

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

}

  1. An infinite loop, from 1 incrementing upward.
  2. calls factor() with each of 1, 2, 3, etc., receives an
  3. array containing that number's factors, and then
  4. 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> 

 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>

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

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

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
Retrieved from "https://rosettacode.org/wiki/Count_in_factors?oldid=168451"