Count in factors: Difference between revisions

 

 

 

=={{header|Ada}}==

 

;count.adb:

procedure Count is

exit when N > Max_N;

end loop;

 

{{out}}

14: 2 x 7

15: 3 x 5</pre>

 

=={{header|AutoHotkey}}==

{{trans|D}}

if n = 1

return 1

Loop 22

out .= A_Index ": " factorize(A_index) "`n"

{{out}}

<pre>1: 1

 

=={{header|AWK}}==

# syntax: GAWK -f COUNT_IN_FACTORS.AWK

BEGIN {

return(substr(f,1,length(f)-1))

}

<p>output:</p>

<pre>

6358=2*11*17*17

</pre>

=={{header|BBC BASIC}}==

PRINT i% " = " FNfactors(i%)

NEXT

ENDWHILE

= LEFT$(f$, LEN(f$) - 3)

Output:

<pre> 1 = 1

19 = 19

20 = 2 x 2 x 5</pre>

 

=={{header|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.

#include <stdlib.h>

 

}

return 0;

{{out}}

<pre>1 = 1

.

.</pre>

 

=={{header|C++}}==

#include <iomanip>

using namespace std;

{

int f = 2; string res;

else

{

{

if( !( li % f ) )

{

li /= f; if( li == 1 ) break;

res += " x ";

int main( int argc, char* argv[] )

{

{

cout << right << setw( 4 ) << x << ": ";

cout << "\n\n";

return system( "pause" );

{{out}}

<pre>

</pre>

 

 

 

=={{header|CoffeeScript}}==

# Count through the natural numbers and give their prime

# factorization. This algorithm uses no division.

 

num_primes = count_primes 10000

 

=={{header|Common Lisp}}==

Auto extending prime list:

(make-array 10 :adjustable t :fill-pointer 0 :element-type 'integer))

 

 

(loop for n from 1 do

{{out}}

<pre>1:

...</pre>

Without saving the primes, and not all that much slower (probably because above code was not well-written):

(loop with res for x from 2 to (isqrt n) do

(loop while (zerop (rem n x)) do

 

(loop for n from 1 do

 

=={{header|D}}==

in {

assert(n > 0);

foreach (i; 1 .. 22)

writefln("%d: %(%d × %)", i, i.factorize());

{{out}}

<pre>1: 1

===Alternative Version===

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

std.array, std.string, import xt.uiprimes;

 

foreach (i; 1 .. 21)

writefln("%2d = %s", i, productStr(factorize(i)));

=={{header|DCL}}==

Assumes file primes.txt is a list of prime numbers;

$ on control_y then $ goto clean

$

$

$ clean:

{{out}}

<pre>$ @count_in_factors

...

2144 = 2*2*2*2*2*67</pre>

 

=={{header|DWScript}}==

begin

if n <= 1 then

var i : Integer;

for i := 1 to 22 do

{{out}}

<pre>1: 1

21: 3 * 7

22: 2 * 11</pre>

 

=={{header|Eiffel}}==

 

class

end

 

Test Output:

 

 

=={{header|Elixir}}==

def factor(n), do: factor(n, 2, [])

 

Enum.each(1..20, fn n ->

 

{{out}}

 

=={{header|Euphoria}}==

sequence result

integer k

end for

printf(1, "%d\n", factors[$])

{{out}}

<pre>1: 1

 

=={{header|F_Sharp|F#}}==

Seq.unfold (fun (f, n) ->

let rec genFactor (f, n) =

let showLines = Seq.concat (seq { yield seq{ yield(Seq.singleton 1)}; yield (Seq.skip 2 (Seq.initInfinite factorsOf))})

 

{{out}}

<pre>1 = 1

2147 = 19 * 113

:

</pre>

 

=={{header|Forth}}==

2

begin 2dup dup * >=

1+ 2 ?do i . ." : " i .factors cr loop ;

 

 

=={{header|Fortran}}==

This algorithm creates a sieve of Eratosthenes, storing the largest prime factor to mark composites. It then finds prime factors by repeatedly looking up the value in the sieve, then dividing by the factor found until the value is itself prime. Using the sieve table to store factors rather than as a plain bitmap was to me a novel idea.

 

!-*- mode: compilation; default-directory: "/tmp/" -*-

!Compilation started at Thu Jun 6 23:29:06

call sieve(0) ! release memory

end program count_in_factors

 

=={{header|Go}}==

 

import "fmt"

fmt.Println()

}

{{out}}

<pre>

 

=={{header|Groovy}}==

if (number == 1) {

return [1]

((1..10) + (6351..6359)).each { number ->

println "$number = ${number.factors().join(' x ')}"

{{out}}

<pre>1 = 1

=={{header|Haskell}}==

Using <code>factorize</code> function from the [[Prime_decomposition#Haskell|prime decomposition]] task,

 

{{out}}

1

2 = 2

121231231232164 = 2 * 2 * 253811 * 119410931

121231231232165 = 5 * 137 * 176979899609

The real solution seems to have to be some sort of a segmented offset sieve of Eratosthenes, storing factors in array's cells instead of just marks. That way the speed of production might not be diminishing as much.

 

=={{header|Icon}} and {{header|Unicon}}==

write("Press ^C to terminate")

every f := [i:= 1] | factors(i := seq(2)) do {

end

 

{{libheader|Icon Programming Library}}

[http://www.cs.arizona.edu/icon/library/src/procs/factors.icn factors.icn provides factors]

16 : [ 2 2 2 2 ]

...</pre>

 

=={{header|J}}==

1 : 1

2 : 2

9 : 3 3

10: 2 5

 

=={{header|Java}}==

{{trans|Visual Basic .NET}}

public static void main(String[] args){

for(int i = 1; i<= 10; i++){

return n;

}

{{out}}

<pre>1 = 1

 

=={{header|JavaScript}}==

console.log(i + " : " + factor(i).join(" x "));

 

}

return factors;

{{out}}

<pre>

10 : 2 x 5

</pre>

 

=={{header|Julia}}==

end

 

 

{{out}}

-4 = -1 × 2 × 2

-3 = -1 × 3

38 = 2 × 19

39 = 3 × 13

</pre>

 

=={{header|Liberty BASIC}}==

'see Run BASIC solution

for i = 1000 to 1016

end if

wend

{{out}}

<pre>

 

=={{header|Lua}}==

if n == 1 then return {1} end

 

end

print ""

 

While[n < 100,

Print[Row[Riffle[Flatten[Map[Apply[ConstantArray, #] &, FactorInteger[n]]],"*"]]];

 

=={{header|NetRexx}}==

{{trans|Java}}

options replace format comments java crossref symbols nobinary

 

end

return

{{out}}

<pre style="height: 30em;overflow: scroll; font-size: smaller;">

=={{header|Nim}}==

{{trans|C}}

 

proc getPrime(idx: int): int =

return primes[idx]

 

stdout.write x, " = "

var n = x

 

let p = getPrime(i)

while n mod p == 0:

n = n div p

stdout.write p

 

if first > 0: echo n

elif n > 1: echo " x ", n

<pre>1 = 1

2 = 2

 

=={{header|Objeck}}==

class CountingInFactors {

function : Main(args : String[]) ~ Nil {

}

}

Output:

<pre>

 

=={{header|OCaml}}==

 

let prime_decomposition x =

aux (succ_big_int v)

in

{{out|Execution}}

<pre>$ ocamlopt -o count.opt nums.cmxa count.ml

=={{header|Octave}}==

Octave's factor function returns an array:

printf ("%i: ", n)

printf ("%i ", factor (n))

printf ("\n")

{{out}}

<pre>1: 1

 

=={{header|PARI/GP}}==

my(f,s="",s1);

if (n < 2, return(n));

s = Str(s, f[1,1]);

if (f[1, 2] != 1, s=Str(s, "^", f[1,2]));

};

 

=={{header|Pascal}}==

{{works with|Free_Pascal}}

 

type

 

function factorize(number: integer): TdynArray;

begin

begin

begin

end;

 

var

writeln;

end;

{{out}}

<pre>

 

=={{header|Perl}}==

{{out}}

<pre>1000000000000000000 = 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 5 x 5 x 5 x 5 x 5 x 5 x 5 x 5 x 5 x 5 x 5 x 5 x 5 x 5 x 5 x 5 x 5 x 5

 

Giving similar output and also good for large inputs:

sub factor {

my ($pn,$pc) = @{Math::Pari::factorint(shift)};

return map { ($pn->[$_]) x $pc->[$_] } 0 .. $#$pn;

}

 

or, somewhat slower and limited to native 32-bit or 64-bit integers only:

 

 

If we want to implement it self-contained, we could use the prime decomposition routine from the [[Prime_decomposition]] task. This is reasonably fast and small, though much slower than the modules and certainly could have more optimization.

my($n, $p, @out) = (shift, 3);

return if $n < 1;

}

 

 

We could use the second extensible sieve from [[Sieve_of_Eratosthenes#Extensible_sieves]] to only divide by primes.

 

sub factors {

}

 

{{out}}

<pre>100000000000 = 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 5 x 5 x 5 x 5 x 5 x 5 x 5 x 5 x 5 x 5 x 5

 

This next example isn't quite as fast and uses much more memory, but it is self-contained and shows a different approach. As written it must start at 1, but a range can be handled by using a <code>map</code> to prefill the <tt>p_and_sq</tt> array.

use utf8;

use strict;

}

die "Ran out of primes?!";

 

 

=={{header|PicoLisp}}==

This is the 'factor' function from [[Prime decomposition#PicoLisp]].

(make

(let (D 2 L (1 2 2 . (4 2 4 2 4 6 2 6 .)) M (sqrt N))

 

(for N 20

{{out}}

<pre>1: 1

 

=={{header|PL/I}}==

cnt: procedure options (main);

declare (i, k, n) fixed binary;

end;

end cnt;

Results:

<pre> 1 = 1

 

=={{header|PowerShell}}==

function eratosthenes ($n) {

if($n -ge 1){

"$(prime-decomposition 100)"

"$(prime-decomposition 12)"

<b>Output:</b>

<pre>

 

=={{header|PureBasic}}==

Protected I = 3, Max

ClearList(Factors())

PrintN(text$)

Next a

{{out}}

<pre> 1= 1

=={{header|Python}}==

This uses the [http://docs.python.org/dev/library/functools.html#functools.lru_cache functools.lru_cache] standard library module to cache intermediate results.

 

primes = [2, 3, 5, 7, 11, 13, 17] # Will be extended

print('\nNumber of primes gathered up to', n, 'is', len(primes))

{{out}}

<pre> 1 1

CacheInfo(hits=3935, misses=7930, maxsize=2000, currsize=2000)</pre>

 

 

 

<pre>

2 = 2

3 = 3

5 = 5

7 = 7

 

 

 

 

 

<br>even though, strictly speaking, it should be &nbsp; '''null'''. &nbsp; &nbsp; &nbsp; &nbsp; The same applies to &nbsp; '''0'''.

 

<br>prime factors are listed, but the number of primes found is always shown. &nbsp; The showing of the count of

<br>primes was included to help verify the factoring (of composites).

say

 

1 = {unity} 1

2 = [prime] 2

11 = [prime] 11

12 = 2 x 2 x 3

13 = [prime] 13

17 = [prime] 17

19 = [prime] 19

23 = [prime] 23

29 = [prime] 29

31 = [prime] 31

37 = [prime] 37

 

12 primes found.

</pre>

<pre>

</pre>

 

=={{header|Ruby}}==

Starting with Ruby 1.9, 'prime' is part of the standard library and provides Integer#prime_division.

require 'prime'

 

end.join " x "

puts "#{i} is #{f}"

{{out|Example}}

<pre>$ ruby prime-count.rb -h

 

=={{header|Run BASIC}}==

print i;" = "; factorial$(i)

next

end if

wend

{{out}}

<pre>1000 = 2 x 2 x 2 x 5 x 5 x 5

1015 = 5 x 7 x 29

1016 = 2 x 2 x 2 x 127</pre>

 

=={{header|Scala}}==

 

 

 

}

 

}

{{out}}

<pre> 1 : 1

 

=={{header|Scheme}}==

(let facs ((l '()) (d 2) (x n))

(cond ((= x 1) (if (null? l) '(1) l))

(display i)

(display " = ")

{{out}}

<pre>1 = 1

 

=={{header|Seed7}}==

 

const proc: writePrimeFactors (in var integer: number) is func

writeln;

end for;

{{out}}

<pre>

 

=={{header|Sidef}}==

method factors(n, p=2) {

}

method is_prime(n) {

self.factors(n).len == 1

}

method next_prime(p) {

}

}

 

 

=={{header|Tcl}}==

This factorization code is based on the same engine that is used in the [[Parallel calculations#Tcl|parallel computation task]].

 

namespace eval prime {

return [join $v "*"]

}

Demonstration code:

for {set i 1} {$i <= $max} {incr i} {

puts [format "%*d = %s" [string length $max] $i [prime::factors.rendered $i]]

 

=={{header|VBScript}}==

Made minor modifications on the code I posted under Prime Decomposition.

If n = 1 Then

CountFactors = 1

WScript.StdOut.WriteLine

WScript.StdOut.Write "2144 = " & CountFactors(2144)

 

{{Out}}

2144 = 2 * 2 * 2 * 2 * 2 * 67

</pre>

 

=={{header|Visual Basic .NET}}==

 

Sub Main()

End Sub

 

{{out}}

<pre>

9999 = 3 x 3 x 11 x 101

10000 = 2 x 2 x 2 x 2 x 5 x 5 x 5 x 5

</pre>

 

=={{header|XPL0}}==

int N0, N, F;

[N0:= 1;

N0:= N0+1;

until KeyHit;

 

Example output:

 

=={{header|zkl}}==

Using the fixed size integer (64 bit) solution from [[Prime decomposition#zkl]]

acc:=fcn(n,k,acc,maxD){ // k is 2,3,5,7,9,... not optimum

if(n==1 or k>maxD) acc.close();

if(n!=m) acc.append(n/m); // opps, missed last factor

else acc;

{{out}}

<pre>

...

</pre>