Count in factors: Difference between revisions

 

=={{header|11l}}==

I li == 1

R ‘1’

L(x) 1..17

print(‘#4: #.’.format(x, get_prime_factors(x)))

 

{{out}}

 

=={{header|360 Assembly}}==

COUNTFAC CSECT assist plig\COUNTFAC

USING COUNTFAC,R13 base register

PG DS CL80 buffer

YREGS

{{out}}

<pre style="height:20ex">

39=3*13

40=2*2*2*5

</pre>

 

 

;count.adb:

procedure Count is

exit when N > Max_N;

end loop;

 

{{out}}

 

=={{header|ALGOL 68}}==

BEGIN

a := c

END;

OD;

print ((new line))

{{out}}

<pre>1 = 1

21 = 3 × 7

22 = 2 × 11</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

Lists the first 100 entries in the sequence. If you wish to extend that, the upper limit is implementation dependent, but may be as low as 130 for an interpreter with signed 8 bit data cells (131 is the first prime outside that range).

 

$<<<^_@#-"e":+1,+55$2<<<

v4_^#-1:/.:g00_00g1+>>0v

 

{{out}}

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

 

=={{header|C sharp|C#}}==

using System.Collections.Generic;

 

}

}

 

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

 

=={{header|Clojure}}==

(:gen-class))

 

(doseq [q (range 1 26)]

(println q " = " (clojure.string/join " x "(factors q))))

{{Output}}

<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|EchoLisp}}==

(define (task (nfrom 2) (range 20))

(for ((i (in-range nfrom (+ nfrom range))))

(writeln i "=" (string-join (prime-factors i) " x "))))

 

{{out}}

<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

 

=={{header|Factor}}==

sequences ;

 

[ " × " write ] [ pprint ] interleave nl ;

 

{{out}}

<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|FreeBASIC}}==

 

Sub getPrimeFactors(factors() As UInteger, n As UInteger)

Print

Print "Press any key to quit"

 

{{out}}

=={{header|Frink}}==

Frink's factoring routines work on arbitrarily-large integers.

while true

{

println[join[" x ", factorFlat[i]]]

i = i + 1

 

=={{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,

 

showFactors n = show n ++ " = " ++ (intercalate " * " . map show . factorize) n

-- Pointfree form

isPrime n = n > 1 && noDivsBy primeNums n

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

 

=={{header|IS-BASIC}}==

110 FOR I=1 TO 30

120 PRINT I;"= ";FACTORS$(I)

280 LET FACTORS$=F$(1:LEN(F$)-1)

290 END IF

{{out}}

<pre> 1 = 1

 

=={{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}}==

function strfactor(n::Integer)

n > -2 || return "-1 × " * strfactor(-n)

for n in lo:hi

@printf("%5d = %s\n", n, strfactor(n))

 

{{out}}

 

=={{header|Kotlin}}==

 

fun isPrime(n: Int) : Boolean {

for (i in list)

println("${"%4d".format(i)} = ${getPrimeFactors(i).joinToString(" * ")}")

 

{{out}}

 

=={{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 ""

 

=={{header|M2000 Interpreter}}==

Decompose function now return array (in number decomposition task return an inventory list).

 

Module Count_in_factors {

Inventory Known1=2@, 3@

}

Count_in_factors

 

=={{header|M4}}==

`ifelse($#,0,``$0'',

`ifelse(eval($2<=$3),1,

 

for(`y',1,25,1, `wby(y)

 

{{out}}

 

=={{header|Maple}}==

local i, j, firstNum;

if n = 1 then

printf("%2a: ", i);

factorNum(i);

{{out}}

<pre>

 

=={{header|Mathematica}} / {{header|Wolfram Language}}==

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 =

stdout.write x, " = "

var n = x

 

for i in 0 ..< int32.high:

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

Typically one would use a module for this. Note that these modules all return an empty list for '1'. This should be efficient to 50+ digits:{{libheader|ntheory}}

{{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|Phix}}==

{{out}}

<pre>

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

Number of primes gathered up to 5000 is 669

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

 

=={{header|R}}==

#initially I created a function which returns prime factors then I have created another function counts in the factors and #prints the values.

 

}

count_in_factors(72)

 

{{out}}

See also [[#Scheme]]. This uses Racket&rsquo;s <code>math/number-theory</code> package

 

 

(require math/number-theory)

(factor-count 1 22)

(factor-count 2140 2150)

 

{{out}}

(formerly Perl 6)

{{works with|rakudo|2015-10-01}}

 

multi factors(1) { 1 }

}

 

The first twenty numbers:

<pre>1: 1

Here is a solution inspired from [[Almost_prime#C]]. It doesn't use &is-prime.

 

$n == 1 ?? 1 !!

gather {

}

 

 

Same output as above.

Alternately, use a module:

 

 

{{out}}

<pre>1 = 1

100000000000000000009 = 557 x 72937 x 2461483384901

100000000000000000010 = 2 x 5 x 11 x 909090909090909091</pre>

 

=={{header|REXX}}==

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

@.=left('', 8); @.0="{unity} "; @.1='[prime] ' /*some tags and handy-dandy literals.*/

parse arg LO HI @ . /*get optional arguments from the C.L. */

end /*j*/

if z==1 then return substr($, 1+length(@) ) /*Is residual=1? Don't add 1*/

{{out|output|text=&nbsp; when using the default inputs:}}

<pre>

 

Note that the &nbsp; '''integer square root''' &nbsp; section of code doesn't use any floating point numbers, just integers.

@.=left('', 8); @.0="{unity} "; @.1='[prime] ' /*some tags and handy-dandy literals.*/

parse arg LO HI @ . /*get optional arguments from the C.L. */

 

if z==1 then return substr($, 1+length(@) ) /*Is residual=1? Don't add 1*/

{{out|output|text=&nbsp; when using the default inputs:}}

<pre>

 

=={{header|Ring}}==

for i = 1 to 20

see "" + i + " = " + factors(i) + nl

end

return left(f, len(f) - 3)

Output:

<pre>

19 = 19

20 = 2 x 2 x 5

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

=={{header|Rust}}==

You can run and experiment with this code at https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=b66c14d944ff0472d2460796513929e2

 

fn main() {

}

vec![n]

{{out}}

<pre>1

20 = 2 x 2 x 5

</pre>

 

=={{header|Scala}}==

object CountInFactors extends App {

 

 

}

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

var a = gather {

for i in (1..100) {

say "#{i} = #{Counter().factors(i).join(' × ')}"

 

=={{header|Swift}}==

 

@inlinable

public func primeDecomposition() -> [Self] {

print("\(i) = \(i.primeDecomposition().map(String.init).joined(separator: " x "))")

}

 

{{out}}

=={{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}}

 

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

 

Sub Main()

End Sub

 

{{out}}

<pre>

</pre>

 

<pre>

</pre>

 

=={{header|Wren}}==

{{libheader|Wren-math}}

 

for (r in [1..9, 2144..2154, 9987..9999]) {

}

System.print()

 

{{out}}

9998: 2 x 4999

9999: 3 x 3 x 11 x 101

</pre>

 

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

=={{header|ZX Spectrum Basic}}==

{{trans|BBC_BASIC}}

20 PRINT i;" = ";

30 IF i=1 THEN PRINT 1: GO TO 90

90 NEXT i

100 STOP