Prime decomposition: Difference between revisions

{{trans|D}}

 

[BigInt] result

V n = number

print(decompose(1023 * 1024))

print(decompose(2 * 3 * 5 * 7 * 11 * 11 * 13 * 17))

 

{{out}}

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

For maximum compatibility, this program uses only the basic instruction set.

USING PRIMEDE,R13

B 80(R15) skip savearea

WDECO DS CL16

YREGS

{{out}}

<pre>

=={{header|AArch64 Assembly}}==

{{works with|as|Raspberry Pi 3B version Buster 64 bits}}

/* ARM assembly AARCH64 Raspberry PI 3B */

/* program primeDecomp64.s */

.include "../includeARM64.inc"

 

{{Output}}

<pre>

 

=={{header|ABAP}}==

public

create public .

ENDIF.

endmethod.

 

=={{header|ACL2}}==

 

(defun prime-factors-r (n i)

(defun prime-factors (n)

(declare (xargs :mode :program))

 

=={{header|Ada}}==

This is the specification of the generic package '''Prime_Numbers''':

 

type Number is private;

Zero : Number;

function Decompose (N : Number) return Number_List;

function Is_Prime (N : Number) return Boolean;

 

The function Decompose first estimates the maximal result length as log₂ of the argument. Then it allocates the result and starts to enumerate divisors. It does not care to check if the divisors are prime, because non-prime divisors will be automatically excluded.

This is the implementation of the generic package '''Prime_Numbers''':

 

-- auxiliary (internal) functions

function First_Factor (N : Number; Start : Number) return Number is

function Is_Prime (N : Number) return Boolean is

(N > One and then First_Factor(N, Two)=N);

 

In the example provided, the package '''Prime_Numbers''' is instantiated with plain integer type:

 

procedure Test_Prime is

begin

Put (Decompose (12));

 

{{out}} (decomposition of 12):

{{works with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d]}}

 

 

MODE LINT = LONG INT;

# OD # ));

done: EMPTY

{{out}}

<pre>

Sadly, ALGOL-M does not allow arrays to be passed as parameters to procedures or functions, so the routine

must store its results in (and know the name of) the external array used for that purpose.

BEGIN

 

 

END

{{out}}

<pre>

 

=={{header|Applesoft BASIC}}==

9050 FOR CA = 2 TO INT( SQR(I))

9060 IF I = 1 THEN RETURN

9210 PF(PF(0)) = CA

9220 I = I / CA

 

=={{header|Arturo}}==

 

facts: to [:string] factors.prime num

print [

]

 

 

{{out}}

 

=={{header|AutoHotkey}}==

factor(n)

f++

}

===Optimized Version===

{{trans|JavaScript}}

if (n <= 3)

return [n]

ans.push(n)

return ans

for i, p in prime_numbers(num)

output .= p " * "

MsgBox % num " = " Trim(output, " * ")

{{out}}

<pre>8388607 = 47 * 178481</pre>

As the examples show, pretty large numbers can be factored in tolerable time:

 

function pfac(n, r, f){

r = ""; f = 2

# For each line of input, print the prime factors.

{ print pfac($1) }

{{out}} entering input on stdin:

<pre>$

=={{header|Batch file}}==

Unfortunately Batch does'nt have a BigNum library so the maximum number that can be decomposed is 2^31-1

@echo off

::usage: cmd /k primefactor.cmd number

set/a compo/=div

goto:loopdiv

 

=={{header|Befunge}}==

{{works_with|befungee}}

Handles safely integers only up to 250 (or ones which don't have prime divisors greater than 250).

> : 11g %!|

> 11g 1+ 11p v

 

=={{header|BQN}}==

An efficient <code>Factor</code> function using trial division and Pollard's rho algorithm is given in bqn-libs [https://github.com/mlochbaum/bqn-libs/blob/master/primes.bqn primes.bqn]. The following standalone version is based on the trial division there, and builds in the sieve from [[Extensible prime generator#BQN|Extensible prime generator]].

# Prime sieve

primes ← ↕0

Try 2

r ∾ 1⊸<⊸⥊n

{{out}}

┌─

╵ 1232123 ⟨ 29 42487 ⟩

1232125 ⟨ 5 5 5 9857 ⟩

1232126 ⟨ 2 7 17 31 167 ⟩

 

=={{header|Burlesque}}==

 

blsq ) 12fC

{2 2 3}

 

=={{header|C}}==

 

Relatively sophiscated sieve method based on size 30 prime wheel. The code does not pretend to handle prime factors larger than 64 bits. All 32-bit primes are cached with 137MB data. Cache data takes about a minute to compute the first time the program is run, which is also saved to the current directory, and will be loaded in a second if needed again.

#include <stdio.h>

#include <stdlib.h>

 

return 0;

 

===Using GNU Compiler Collection gcc extensions===

way, and in the case of this sample it requires the GCC "nested procedure"

extension to the C language.

#include <stdio.h>

#include <math.h>

CONTINUE;

}

{{out}}

<pre>

Note: gcc took 487,719 BogoMI to complete the example.

 

#include <stdlib.h>

#include <stdint.h>

return 0;

 

 

===Version 2===

typedef unsigned long long int ulong; // define a type that represent the limit (64-bit)

 

}

 

 

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

using System.Collections.Generic;

 

}

}

 

===Simple trial division===

Although this three-line algorithm does not mention anything about primes, the fact that factors are taken out of the number <code>n</code> in ascending order garantees the list will only contain primes.

 

 

namespace PrimeDecomposition

return factors;

}

 

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

{{works with|g++|4.1.2 20061115 (prerelease) (Debian 4.1.1-21)}}

{{libheader|GMP}}

#include <gmpxx.h>

 

std::cout << "\n";

}

 

=== Simple trial division ===

 

#include <iostream>

}

return 0;

 

=={{header|Clojure}}==

(defn factors

"Return a list of factors of N."

(if (= 0 (rem n k))

(recur (quot n k) k (cons k acc))

 

=={{header|Commodore BASIC}}==

{{works_with|Commodore BASIC|2.0}}

It's not easily possible to have arbitrary precision integers in PET basic, so here is at least a version using built-in data types (reals). On return from the subroutine starting at 9000 the global array pf contains the number of factors followed by the factors themselves:

9010 REM in ... i ... number

9020 REM out ... pf() ... factors

9210 pf(pf(0))=ca

9220 i=i/ca

 

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

(defun factor (n)

"Return a list of factors of N."

for d = 2 then (if (evenp d) (+ d 1) (+ d 2)) do

(cond ((> d max-d) (return (list n))) ; n is prime

 

(defun factor (n &optional (acc '()))

(when (> n 1) (loop with max-d = (isqrt n)

(list (caar acc) (1+ (cadar acc)))

(cdr acc))

 

=={{header|D}}==

 

Unqual!T[] decompose(T)(in T number) pure nothrow

decompose(16860167264933UL.BigInt * 179951).writeln;

decompose(2.BigInt ^^ 100_000).group.writeln;

{{out}}

<pre>[2]

{{libheader| System.SysUtils}}

{{Trans|C#}}

program Prime_decomposition;

 

write(v, ' ');

readln;

 

=={{header|E}}==

This example assumes a function <code>isPrime</code> and was tested with [[Primality by Trial Division#E|this one]]. It could use a self-referential implementation such as the Python task, but the original author of this example did not like the ordering dependency involved.

 

var primesCache := [2]

/** A collection of all prime numbers. */

}

return factors

 

=={{header|EchoLisp}}==

The built-in '''prime-factors''' function performs the task.

→ (2 2 2 2 2 2 2 2 2 2)

 

 

(prime-factors 100000000000000000037)

 

=={{header|Eiffel}}==

Uses the feature prime from the Task Primality by Trial Devision in the contract to check if the Result contains only prime numbers.

PRIME_DECOMPOSITION

 

is_divisor: across Result as r all p \\ r.item = 0 end

is_prime: across Result as r all prime (r.item) end

 

The test was done in an application class. (Similar as in other Eiffel examples (ex. Selectionsort).)

=={{header|Ela}}==

{{trans|F#}}

 

decompose_prime n = loop n 2I

| else = loop c (p + 1I)

 

 

{{out}}<pre>[71,839,1471,6857]</pre>

 

=={{header|Elixir}}==

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

Enum.each(mersenne, fn {n,m} ->

:io.format "~3s :~20w = ~s~n", ["M#{n}", m, Prime.decomposition(m) |> Enum.join(" x ")]

 

{{out}}

 

=={{header|Erlang}}==

 

factors(N) ->

factors(N div K,K, [K|Acc]);

factors(N,K,Acc) ->

 

=={{header|ERRE}}==

PROGRAM DECOMPOSE

 

PRINT

END PROGRAM

This version is a translation from Commodore BASIC program.

 

=={{header|Ezhil}}==

## இந்த நிரல் தரப்பட்ட எண்ணின் பகாஎண் கூறுகளைக் கண்டறியும்

 

 

பதிப்பி "நீங்கள் தந்த எண்ணின் பகா எண் கூறுகள் இவை: ", பகாஎண்கூறுகள்

 

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

let rec loop c p =

if c < (p * p) then [c]

loop n 2I

{{out}}

<pre>[71; 839; 1471; 6857]</pre>

=={{header|Factor}}==

<code>factors</code> from the <code>math.primes.factors</code> vocabulary converts a number into a sequence of its prime divisors; the rest of the code prints this sequence.

 

27720 factors

[ number>string ] map

 

=={{header|FALSE}}==

 

=={{header|Forth}}==

2

begin 2dup dup * >=

then

repeat

 

=={{header|Fortran}}==

{{works with|Fortran|90 and later}}

implicit none

 

end subroutine find_factors

 

 

use PrimeDecompose

implicit none

end do

 

 

=={{header|FreeBASIC}}==

 

Function isPrime(n As Integer) As Boolean

Print

Print "Press any key to quit"

 

{{out}}

Frink has a built-in factoring function which uses wheel factoring, trial division, Pollard p-1 factoring, and Pollard rho factoring.

It also recognizes some special forms (e.g. Mersenne numbers) and handles them efficiently.

 

{{out}} (total process time including JVM startup = 1.515 s):

=={{header|GAP}}==

Built-in function :

Or using the [http://www.gap-system.org/Manuals/pkg/factint/doc/chap0.html FactInt] package :

 

=={{header|Go}}==

 

import (

fmt.Println(v, "->", Primes(big.NewInt(v)))

}

{{out}}

<pre>2147483648 -> [2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2]

so it does not require an "isPrime-like function",

assumed or otherwise.

if (target == 1) return [1L]

}

primeFactors

 

{{out|Test #1}}

 

{{out|Output #1}}

 

{{out|Test #2}}

 

{{out|Output #2}}

The task description hints at using the <code>isPrime</code> function from the [[Primality by trial division#Haskell|trial division]] task:

 

-- [2..n] >>= (\p-> [p|isPrime p]) >>= divs n

where

divs n p | rem n p == 0 = p : divs (quot n p) p

 

but it is not very efficient, to put it mildly. Inlining and fusing gets us the progressively more optimized

import Data.List (unfoldr)

 

takeWhile ((<=n).(^2)) [d..] ++ [n|n>1], mod n x==0]) (2,n)

= unfoldr (\(ds,n) -> listToMaybe [(x, (dropWhile (< x) ds, div n x)) | n>1, x <-

 

The library function <code>listToMaybe</code> gets at most one element from its list argument. The last variant can be written as the optimal

 

where

divs n ds@(d:t) | d*d > n = [n | n > 1]

| r == 0 = d : divs q ds

| otherwise = divs n t

 

See [[Sieve of Eratosthenes]] or [[Primality by trial division]] for a source of primes to use with this function.

 

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

factors := primedecomp(2^43-1) # a big int

end

end

 

 

{{libheader|Icon Programming Library}} [http://www.cs.arizona.edu/icon/library/src/procs/factors.icn Uses genfactors and prime from factors]

 

=={{header|J}}==

 

{{out|Example use}}

 

and, more elaborately:

 

340282366920938463463374607431768211455

q: _1+2^128x

3 5 17 257 641 65537 274177 6700417 67280421310721

*/ q: _1+2^128x

 

=={{header|Java}}==

This is a version for arbitrary-precision integers

which assumes the existence of a function with the signature:

You will need to import java.util.List, java.util.LinkedList, and java.math.BigInteger.

List<BigInteger> ans = new LinkedList<BigInteger>();

//loop until we test the number itself or the number is 1

}

return ans;

 

Alternate version, optimised to be faster.

 

public List<BigInteger> primeDecomp(BigInteger a) {

}

return result;

 

Another alternate version designed to make fewer modular calculations:

private static final BigInteger TWO = BigInteger.valueOf(2);

private static final BigInteger THREE = BigInteger.valueOf(3);

return factors;

}

{{trans|C#}}

Simple but very inefficient method,

because it will test divisibility of all numbers from 2 to max prime factor.

When decomposing a large prime number this will take O(n) trial divisions instead of more common O(log n).

List<BigInteger> ans = new LinkedList<BigInteger>();

 

}

return ans;

 

=={{header|JavaScript}}==

This code uses the BigInteger Library [http://xenon.stanford.edu/~tjw/jsbn/jsbn.js jsbn] and [http://xenon.stanford.edu/~tjw/jsbn/jsbn2.js jsbn2]

var n = new BigInteger(input.value, 10);

var TWO = new BigInteger("2", 10);

divisor = divisor.add(TWO);

}

 

Without any library.

if (n <= 3)

return [n];

ans.push(n);

return ans;

 

TDD using Jasmine

 

PrimeFactors.js

if (!n || n < 2)

return [];

return f;

};

 

SpecPrimeFactors.js (with tag for Chutzpah)

 

describe("Prime Factors", function() {

});

});

 

=={{header|jq}}==

reliable for integers up to and including 9,007,199,254,740,992 (2^53). However, "factors"

could be easily modified to work with a "BigInt" library for jq, such as [https://gist.github.com/pkoppstein/d06a123f30c033195841 BigInt.jq].

. as $in

| [2, $in, false]

end

end )

'''Examples''':

24 | factors

#=> 2 2 2 3

# 2**29-1 is 536870911

[ 536870911 | factors ]

 

=={{header|Julia}}==

using package Primes.jl:

julia> Pkg.add("Primes")

julia> factor(8796093022207)

[9719=>1,431=>1,2099863=>1]

(The <code>factor</code> function returns a dictionary

whose keys are the factors and whose values are the multiplicity of each factor.)

 

=={{header|Kotlin}}==

 

import java.math.BigInteger

println("2^${"%2d".format(prime)} - 1 = ${bigPow2.toString().padEnd(30)} => ${getPrimeFactors(bigPow2)}")

}

 

{{out}}

 

=={{header|Lambdatalk}}==

{def prime_fact.smallest

{def prime_fact.smallest.r

86:[2,43] 87:[3,29] 88:[2,2,2,11] 89:[89] 90:[2,3,3,5] 91:[7,13] 92:[2,2,23] 93:[3,31] 94:[2,47] 95:[5,19] 96:[2,2,2,2,2,3]

97:[97] 98:[2,7,7] 99:[3,3,11] 100:[2,2,5,5] 101:[101]

 

=={{header|LFE}}==

 

(defun factors (n)

(factors n 2 '()))

((n k acc)

(factors n (+ k 1) acc)))

 

=={{header|Lingo}}==

-- To overcome the limits of integers (signed 32-bit in Lingo),

-- the number can be specified as float (which works up to 2^53).

f.add(n)

return f

-- [2.0000, 2.0000, 3.0000]

 

 

put getPrimeFactors(1125899906842623.0)

 

=={{header|Logo}}==

if :p*:p > :n [output (list :n)]

if less? 0 modulo :n :p [output (decompose :n bitor 1 :p+1)]

output fput :p (decompose :n/:p :p)

 

=={{header|Lua}}==

is located at [[Primality by trial division#Lua]]

 

local f = {}

return f

 

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

Module Prime_decomposition {

Inventory Known1=2@, 3@

}

Prime_decomposition

 

=={{header|Maple}}==

of prime factors and their multiplicities:

 

(7) (191)

[1, [[7, 1], [191, 1]]]

 

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

Bare built-in function does:

 

Read as: 2 to the power 5 times 3 squared times 7 (to the power 1).

To show them nicely we could use the following functions:

 

Example for small prime:

gives:

 

Examples for large primes:

gives back:

0.000231 sec

1152921504606846975 = 3^2 5^2 7 11 13 31 41 61 151 331 1321

0.009419 sec

1427247692705959881058285969449495136382746623 = 3^2 7 11 31 151 251 331 601 1801 4051 100801 10567201 1133836730401

 

=={{header|MATLAB}}==

 

=={{header|Maxima}}==

Using the built-in function:

(%i2) factor(2016);

(%o2) 2^5*3^2*7

Using the underlying language:

 

/* or, slighlty more "functional" */

 

prime_dec(2^4*3^5*5*7^2);

 

=={{header|MUMPS}}==

SET HI=HI\1

KILL ERATO1 ;Don't make it new - we want it to remain after the quit

IF I>1 SET PRIMDECO=$S($L(PRIMDECO)>0:PRIMDECO_"^",1:"")_I D PRIMDECO(N/I)

;that is, if I is a factor of N, add it to the string

{{out|Usage}}

<pre>USER>K ERATO1,PRIMDECO D PRIMDECO^ROSETTA(31415) W PRIMDECO

=={{header|Nim}}==

Based on python floating point solution, but using integers rather than floats.

 

proc getStep(n: int64): int64 {.inline.} =

let start = cpuTime()

stdout.write primeFac(p).join(", ")

 

{{out}}

 

=={{header|OCaml}}==

 

let prime_decomposition x =

inner (succ_big_int c) p

in

 

=={{header|Octave}}==

 

=={{header|Oforth}}==

Oforth handles aribitrary precision integers.

 

| k p |

ListBuffer new

]

n 1 > ifTrue: [ n over add ]

 

{{out}}

Thus <code>factor(12)==[2,2;3,1]</code> is true.

But it's simple enough to convert this to a vector with repetition:

my(f=factor(n),v=f[,1]~);

for(i=1,#v,

);

vecsort(v)

 

=={{header|Pascal}}==

 

type

for j := low(factors) to high(factors) do

writeln (factors[j]);

{{out}}

<pre>% ./PrimeDecomposition

'''Optimization:'''

 

 

type

writeln (factors[j]);

readln;

 

=={{header|Perl}}==

 

===Trivial trial division (very slow)===

my ($n, $d, @out) = (shift, 1);

while ($n > 1 && $d++) {

}

 

 

===Better trial division===

This is ''much'' faster than the trivial version above.

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

return if $n < 1;

push @out, $n if $n > 1;

@out;

 

===Modules===

These both take about 1 second to factor all Mersenne numbers from M_1 to M_150.

{{libheader|ntheory}}

use bigint;

 

my $p = 2 ** $_ - 1;

print "2**$_-1: ", join(" ", factor($p)), "\n";

{{out}}

<pre>

 

{{libheader|Math::Pari}}

 

# Convert Math::Pari's format into simple vector

my $p = 2 ** $_ - 1;

print "2^$_-1: ", join(" ", factor($p)), "\n";

With the same output.

 

For small numbers less than 2<small>⁵³</small> on 32bit and 2<small>⁶⁴</small> on 64bit just use prime_factors().

{{libheader|Phix/mpfr}}

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #7060A8;">requires</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"1.0.0"</span><span style="color: #0000FF;">)</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>

<span style="color: #0000FF;">?</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)</span>

{{out}}

<pre>

 

=={{header|Picat}}==

% Checking 2**prime-1

foreach(P in primes(60))

Divisors := Divisors ++ [Div],

M := M div Div

 

{{out}}

17 19 23 29 31 37 ..), as described by Donald E. Knuth, "The Art of Computer

Programming", Vol.2, p.365.

(make

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

(link N) ) ) )

 

{{out}}

<pre>-> (3 11 31 131 2731 8191 409891 7623851 145295143558111)</pre>

 

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

test: procedure options (main, reorder);

declare (n, i) fixed binary (31);

 

end test;

{{out|Results from various runs}}

<pre>

 

=={{header|PowerShell}}==

function eratosthenes ($n) {

if($n -gt 1){

"$(prime-decomposition 12)"

"$(prime-decomposition 100)"

<b>Output:</b>

<pre>

 

=={{header|Prolog}}==

SN is sqrt(N),

prime_decomp_1(N, SN, 2, [], L).

prime_decomp_2(N, SN, D1, L, LF)

)

 

{{out}}

% 138,882 inferences, 0.344 CPU in 0.357 seconds (96% CPU, 404020 Lips)

L = [20394401,69431,6361].

?- time(prime_decomp(1361129467683753853853498429727072845823, L)).

% 18,080,807 inferences, 7.953 CPU in 7.973 seconds (100% CPU, 2273422 Lips)

 

====Simple version====

Optimized to stop on square root, and count by +2 on odds, above 2.

 

factors2( N, FS).

; 0 is N rem K -> FS = [K|FS2], N2 is N div K, factors( N2, K, FS2)

; K2 is K+2, factors( N, K2, FS)

 

====Expression Tree version====

Uses a 2*3*5*7 factor wheel, but the main feature is that it returns the decomposition as a fully simplified expression tree.

wheel2357(L) :-

W = [2, 4, 2, 4, 6, 2, 6, 4,

reverse_factors(A*B, C*A) :- reverse_factors(B, C), !.

reverse_factors(A, A).

{{Out}}

<pre>

 

=={{header|Pure}}==

factor k n = k : factor k (n div k) if n mod k == 0;

= if n>1 then [n] else [] if k*k>n;

= factor (k+1) n if k==2;

= factor (k+2) n otherwise;

 

=={{header|PureBasic}}==

{{works with|PureBasic|4.41}}

CompilerIf #PB_Compiler_Debugger

CompilerError "Turn off the debugger if you want reasonable speed in this example."

S + #CRLF$ + Str(Factors())

Next

{{out}}

<pre>Factored 9007199254740991 in 0.27 seconds.

Note: the program below is saved to file <code>prime_decomposition.py</code> and imported as a library [[Least_common_multiple#Python|here]], [[Semiprime#Python|here]], [[Almost_prime#Python|here]], [[Emirp primes#Python|here]] and [[Extensible_prime_generator#Python|here]].

 

 

import sys

print( "=> {0:.2f}s".format( time.time()-start ) )

if m >= 59:

{{out}}

<pre>2**2-1 = 3, with factors:

Here a shorter and marginally faster algorithm:

 

try:

long

tocalc = 2**59-1

print("%s = %s" % (tocalc, fac(tocalc)))

 

{{out}}

=={{header|Quackery}}==

 

dup times

[ [ dup i^ 2 + /mod

drop ] is primefactors ( n --> [ )

 

 

{{out}}

 

=={{header|R}}==

x <- NULL

firstprime<- 2; secondprime <- 3; everyprime <- num

}

 

 

Or a more explicit (but less efficient) recursive approach:

 

===Recursive Approach (Less efficient for large numbers)===

primes <- as.integer(c())

 

}

}

=== Alternate solution ===

a <- NULL

if (n > 1) {

}

a

 

=={{header|Racket}}==

#lang racket

(require math)

(define (factors n)

(append-map (λ (x) (make-list (cadr x) (car x))) (factorize n)))

 

Or, an explicit (and less efficient) computation:

#lang racket

(define (factors number)

(let-values ([(q r) (quotient/remainder n i)])

(if (zero? r) (cons i (loop q i)) (loop n (add1 i)))))))

 

=={{header|Raku}}==

This is a pure Raku version that uses no outside libraries. It uses a variant of Pollard's rho factoring algorithm and is fairly performent when factoring numbers < 2⁸⁰; typically taking well under a second on an i7. It starts to slow down with larger numbers, but really bogs down factoring numbers that have more than 1 factor larger than about 2⁴⁰.

 

return $n if $n.is-prime;

return () if $n == 1;

"factors of $n: ",

prime-factors($n).join(' × '), " \t in ", (now - $start).fmt("%0.3f"), " sec."

 

{{out}}

===External library===

If you really need a speed boost, load the highly optimized Perl 5 ntheory module. It needs a little extra plumbing to deal with the lack of built-in big integer support, but for large number factoring the interface overhead is worth it.

my $p5 = Inline::Perl5.new();

$p5.use( 'ntheory' );

say "factors of $n: ",

prime-factors($n).join(' × '), " \t in ", (now - $start).fmt("%0.3f"), " sec."

{{out}}

<pre>factors of 536870911: 233 × 1103 × 2089 in 0.001 sec.

Since the majority of computing time is spent looking for primes, that part of the program was

<br>optimized somewhat (but could be extended if more optimization is wanted).

numeric digits 1000 /*handle thousand digits for the powers*/

parse arg bot top step base add /*get optional arguments from the C.L. */

/* [↓] The $ list has a leading blank.*/

if x==1 then return $ /*Is residual=unity? Then don't append.*/

'''output''' &nbsp; when using the default input of: &nbsp; <tt> 1 &nbsp; 100 </tt>

 

===optimized more===

This REXX version is about &nbsp; '''20%''' &nbsp; faster than the 1^st REXX version when factoring one million numbers.

numeric digits 1000 /*handle thousand digits for the powers*/

parse arg bot top step base add /*get optional arguments from the C.L. */

/* [↓] The $ list has a leading blank.*/

if x==1 then return $ /*Is residual=unity? Then don't append.*/

'''output''' &nbsp; is identical to the 1^st REXX version. <br><br>

 

=={{header|Ring}}==

prime = 18705

decomp(prime)

next

return 1

 

=={{header|Ruby}}==

===Built in===

=> true

irb(main):003:0> 2543821448263974486045199.prime_division

 

===Simple algorithm===

# This routine is terribly inefficient, but elegance rules.

def prime_factors(i)

factors = prime_factors(2**i-1)

puts "2**#{i}-1 = #{2**i-1} = #{factors.join(' * ')}"

{{out}}

<pre>...

 

===Faster algorithm===

# This routine is more efficient than prime_factors,

# and quite similar to Integer#prime_division of MRI 1.9.

factors = prime_factors_faster(2**i-1)

puts "2**#{i}-1 = #{2**i-1} = #{factors.join(' * ')}"

{{out}}

<pre>...

This benchmark compares the different implementations.

 

require 'mathn'

Benchmark.bm(24) do |x|

x.report(" Integer#prime_division") { i.prime_division }

end

 

With [[MRI]] 1.8, ''prime_factors'' is slow, ''Integer#prime_division'' is fast, and ''prime_factors_faster'' is very fast. With MRI 1.9, Integer#prime_division is also very fast.

The implementation:

 

use num_traits::{One, Zero};

use std::fmt::{Display, Formatter};

}

}

 

=={{header|S-BASIC}}==

rem - return p mod q

function mod(p, q = integer) = integer

end

{{out}}

<pre>

=={{header|Scala}}==

{{libheader|Scala}}

import collection.parallel.mutable.ParSeq

 

}

}

{{out}}

<pre>

Since the problems seems to ask for it, here is one version that does it:

 

val zero = BigInt(0)

val one = BigInt(1)

 

def hasNext = currentN != one && currentN > zero

 

The method isProbablePrime(n) has a chance of 1 - 1/(2^n) of correctly

Next is a version that does not depend on identifying primes,

and works with arbitrary integral numbers:

import num._

val two = one + one

 

def hasNext = currentN != one && currentN > zero

{{out}}

Both versions can be rather slow, as they accept arbitrarily big numbers,

 

Alternatively, Scala LazyLists and Iterators support quite elegant one-line encodings of iterative/recursive algorithms, allowing us to to define the prime factorization like so:

import spire.implicits._

 

=={{header|Scheme}}==

(define (*factor divisor number)

(if (> (* divisor divisor) number)

 

(display (factor 111111111111))

{{out}}

(3 7 11 13 37 101 9901)

 

=={{header|Seed7}}==

result

var array integer: result is 0 times 0;

result &:= [](number);

end if;

 

Original source: [http://seed7.sourceforge.net/algorith/math.htm#factorise]

'''Recursive Using isPrime'''

 

 

primeFactorization(num) := primeFactorizationHelp(num, []);

current when size(primeFactors) = 0

else

 

Using isPrime Based On: [https://www.youtube.com/watch?v=CsCBkPg1FbE]

'''Recursive Trial Division'''

 

 

primeFactorizationHelp(num, divisor, factors(1)) :=

primeFactorizationHelp(num, divisor + 1, factors) when num mod divisor /= 0

else

 

=={{header|Sidef}}==

Built-in:

 

Trial division:

return [] if (n < 1)

gather {

take(n) if (n > 1)

}

 

Calling the function:

 

=={{header|Simula}}==

Simula has no built-in function to test for prime numbers.<br>

Code for class bignum can be found here: https://rosettacode.org/wiki/Pi#Simula

EXTERNAL CLASS BIGNUM;

BIGNUM

 

END;

{{out}}

<pre>

=={{header|Slate}}==

Admittedly, this is just based on the Smalltalk entry below:

"Decomposes the Integer into primes, applying the block to each (in increasing

order)."

[div: next.

next: next + 2] "Just look at the next odd integer."

 

=={{header|Smalltalk}}==

 

primesDo: aBlock [

| div next rest |

]

]

 

=={{header|SPAD}}==

{{works with|FriCAS, OpenAxiom, Axiom}}

 

(1) -> factor 102400

Type: Factored(Integer)

 

 

Domain:[http://fricas.github.io/api/Factored.html?highlight=factor Factored(R)]

=={{header|Standard ML}}==

Trial division

val factor = fn n :IntInf.int =>

let

 

end;

<pre>

- Array.fromList(factor 122489234920000001278234798233);;

The following Mata function will factor any representable positive integer (that is, between 1 and 2^53).

 

n = n_

a = J(0,2,.)

return(a)

}

 

=={{header|Swift}}==

Uses the sieve of Eratosthenes. This is generic on any type that conforms to BinaryInteger. So in theory any BigInteger library should work with it.

 

guard n > 2 else { return [] }

 

 

print("2^\(prime) - 1 = \(m) => \(decom)")

 

{{out}}

 

=={{header|Tcl}}==

# list the prime factors of x in ascending order

set result [list]

return $result

}

Testing

set n [expr {2**$m - 1}]

catch {time {set primes [factors $n]} 1} tm

puts [format "2**%02d-1 = %-18s = %-22s => %s" $m $n [join $primes *] $tm]

{{out}}

<pre>2**02-1 = 3 = 3 => 184 microseconds per iteration

 

=={{header|TI-83 BASIC}}==

Disp "FACTEURS PREMIER"

Prompt N

sub(Str0,4,O-3)→Str0

ClrList L5,L6

{{out}}

<pre>

 

=={{Header|Tiny BASIC}}==

20 INPUT N

25 PRINT "------"

300 LET N = N / I

310 PRINT I

{{out}}

<pre>

{{trans|Common Lisp}}

 

@(do

(defun factor (n)

@(output)

@num -> {@(rep)@factors, @(last)@factors@(end)}

{{out}}

<pre>$ txr factor.txr 1139423842450982345

=={{header|V}}==

like in scheme (using variables)

[inner [c p] let

[c c * p >]

ifte]

ifte].

 

(mostly) the same thing using stack (with out variables)

[inner

[dup * <]

ifte]

ifte].

 

Using it

=[3 11 37]

 

=={{header|VBScript}}==

arrP = Split(ListPrimes(n)," ")

divnum = n

 

WScript.StdOut.Write PrimeFactors(CInt(WScript.Arguments(0)))

 

{{out}}

{{libheader|Wren-fmt}}

The examples are borrowed from the Go solution.

import "/fmt" for Fmt

 

for (val in vals) {

Fmt.print("$10d -> $n", val, BigInt.primeFactors(val))

 

{{out}}

=={{header|XSLT}}==

Let's assume that in XSLT the application of a template is similar to the invocation of a function. So when the following template

 

<xsl:template match="/numbers">

</xsl:template>

 

is applied against the document

<number><value>1</value></number>

<number><value>2</value></number>

<number><value>9</value></number>

<number><value>255</value></number>

then the output contains the prime decomposition of each number:

<body>

<ul>

</ul>

</body>

 

=={{header|zkl}}==

With 64 bit ints:

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;

9007199254740991, 576460752303423487)){

println(n,": ",primeFactors(n).concat(", "))

{{out}}

<pre>

</pre>

Unfortunately, big ints (GMP) don't have (quite) the same interface as ints (since there is no big float, BI.toFloat() truncates to a double so BI.toFloat().sqrt() is wrong). So mostly duplicate code is needed:

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;

foreach n in (T(BN("12"),

BN("340282366920938463463374607431768211455"))){

println(n,": ",factorsBI(n).concat(", "))

{{out}}

<pre>