Factors of an integer: Difference between revisions

=={{header|0815}}==

<:1:~>|~#:end:>~x}:str:/={^:wei:~%x<:a:x=$~

=}:wei:x<:1:+{>~>x=-#:fin:^:str:}:fin:{{~%

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

{{trans|Python}}

V factors = Set[Int]()

L(x) 1..Int(sqrt(n))

L(i) (45, 53, 64)

{{out}}

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

Very compact version.

FACTOR CSECT

USING FACTOR,R15 set base register

PG DC CL132' ' buffer

YREGS

{{out}}

<pre>

=={{header|68000 Assembly}}==

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

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

/* ARM assembly AARCH64 Raspberry PI 3B */

/* program factorst64.s */

.include "../includeARM64.inc"

=={{header|ACL2}}==

(declare (xargs :measure (nfix (- n i))))

(cond ((zp (- n i))

(defun factors (n)

=={{header|Action!}}==

BYTE notFirst

CARD p

Test(6502)

Test(12345)

{{out}}

[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Factors_of_an_integer.png Screenshot from Atari 8-bit computer]

=={{header|ActionScript}}==

{

var factors:Vector.<uint> = new Vector.<uint>();

if(n % i == 0)factors.push(i);

return factors;

=={{header|Ada}}==

with Ada.Command_Line;

procedure Factors is

end loop;

Ada.Text_IO.Put_Line (Positive'Image (Number) & ".");

=={{header|Aikido}}==

function factor (n:int) {

printvec (factor (45))

printvec (factor (25))

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

Note: The following implements generators, eliminating the need of declaring arbitrarily long '''int''' arrays for caching.

PROC gen factors = (INT n, YIELDINT yield)VOID: (

# OD # ));

print(new line)

{{out}}

<pre>

=={{header|ALGOL W}}==

% return the factors of n ( n should be >= 1 ) in the array factor %

% the bounds of factor should be 0 :: len (len must be at least 1) %

for i := 1 until 100 do testFactorsOf( i )

{{out}}

<pre>

=={{header|ALGOL-M}}==

Instead of displaying 1 and the number itself as factors, prime numbers are explicitly reported as such. To reduce the number of test divisions, only odd divisors are tested if an initial check shows the number to be factored is not even. The upper limit of divisors is set at N/2 or N/3, depending on whether N is even or odd, and is continuously reduced to N divided by the next potential divisor until the first factor is found. For a prime number the resulting limit will be the square root of N, which avoids the necessity of explicitly calculating that value. (ALGOL-M does not have a built-in square root function.)

BEGIN

DONE: WRITE ("GOODBYE");

{{out}}

<pre>NUMBER TO FACTOR (OR 0 TO QUIT):

=={{header|APL}}==

factors 12345

1 3 5 15 823 2469 4115 12345

factors 720

=={{header|AppleScript}}==

===Functional===

{{Trans|JavaScript}}

on integerFactors(n)

if n = 1 then

end script

end if

{{Out}}

----

===Straightforward===

set output to {}

end factors

{{output}}

=={{header|Arc}}==

(= divisor (fn (num)

(= dlist '())

(map [rev _] (map [divisor _] '(45 53 60 64)))

{{Out}}

'(

(1 3 5 9 15 45)

(1 2 4 8 16 32 64)

)

=={{header|ARM Assembly}}==

{{works with|as|Raspberry Pi}}

/* ARM assembly Raspberry PI */

/* program factorst.s */

=={{header|Arturo}}==

select 1..num [x][

(num%x)=0

]

{{out}}

=={{header|Asymptote}}==

for(var j : n) {

}

write(" ", j);

{{out}}

<pre>11 => 1 11

=={{header|AutoHotkey}}==

Factors(n)

Sort, v, N U D,

Return, v

{{out}}

=={{header|AutoIt}}==

$num = 45

MsgBox (0,"Factors", "Factors of " & $num & " are: " & factors($num))

Next

Return $ls_factors&$intg

{{out}}

=={{header|AWK}}==

# syntax: GAWK -f FACTORS_OF_AN_INTEGER.AWK

BEGIN {

printf("\n")

}

{{out}}

Note that this will error out if you pass 32767 (or higher).

REDIM SHARED factors(0) AS INTEGER

END IF

NEXT

{{out}}

==={{header|ASIC}}===

{{trans|GW-BASIC}}

REM Factors of an integer

PRINT "Enter an integer";

NEXT I

PRINT NA

{{out}}

<pre>

==={{header|BASIC256}}===

{{trans|FreeBASIC}}

subroutine printFactors(n)

print n; " => ";

call printFactors(96)

end

{{out}}

<pre>

==={{header|GW-BASIC}}===

10 INPUT "Enter an integer: ", N

20 IF N = 0 THEN GOTO 10

50 IF NA MOD I = 0 THEN PRINT I;

60 NEXT I

{{out}}

<pre>

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

110 INPUT PROMPT "Number: ":N

120 FOR I=1 TO INT(N/2)

130 IF MOD(N,I)=0 THEN PRINT I;

140 NEXT

==={{header|Minimal BASIC}}===

{{works with|Commodore BASIC}}

{{works with|Nascom ROM BASIC|4.7}}

10 REM Factors of an integer

20 PRINT "Enter an integer";

100 PRINT N1

110 END

==={{header|Nascom BASIC}}===

{{trans|GW-BASIC}}

{{works with|Nascom ROM BASIC|4.7}}

10 REM Factors of an integer

20 INPUT "Enter an integer"; N

80 PRINT NA

90 END

{{out}}

<pre>

==={{header|Sinclair ZX81 BASIC}}===

{{works with|Applesoft BASIC}}

20 FOR I=1 TO N

30 IF N/I=INT (N/I) THEN PRINT I;" ";

{{in}}

<pre>315</pre>

==={{header|Tiny BASIC}}===

110 INPUT I

120 LET C=1

150 LET C=C+1

160 IF C<=I THEN GOTO 140

{{out}}

<pre>Give me a number:

==={{header|True BASIC}}===

{{trans|FreeBASIC}}

sub printfactors(n)

if n < 1 then exit sub

print

end

{{out}}

<pre>

=={{header|Batch File}}==

Command line version:

set res=Factors of %1:

for /L %%i in (1,1,%1) do call :fac %1 %%i

:fac

set /a test = %1 %% %2

{{out}}

Interactive version:

set /p limit=Gimme a number:

set res=Factors of %limit%:

:fac

set /a test = %1 %% %2

{{out}}

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

{{works with|BBC BASIC for Windows}}

sort% = FN_sortinit(0, 0)

L$ += STR$(L%(I%)) + ", "

NEXT

{{out}}

=={{header|bc}}==

* This function mutates the global array f[] which will

* contain all factors of n in ascending order after the call!

scale = o

return(l)

=={{header|Befunge}}==

>:0:g:*`| > >0:g1+0:p

>:0:g:*-#v_0:g\>$>:!#@_.v

=={{header|BQN}}==

A bqncrate idiom.

•Show Factors 12345

The [https://github.com/mlochbaum/bqn-libs/blob/master/primes.bqn primes] library from bqn-libs can be used for a solution that's more efficient for large inputs. <code>FactorExponents</code> returns each unique prime factor along with its exponent.

=={{header|Burlesque}}==

=={{header|C}}==

#include <stdlib.h>

}

return 0;

===Prime factoring===

#include <stdlib.h>

#include <string.h>

return 0;

{{out}}

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

===C# 1.0===

do {

Console.WriteLine ("Number:");

Console.WriteLine ("Done.");

} while (true);

===C# 3.0===

using System.Collections.Generic;

using System.Linq;

Console.WriteLine (String.Join (", ", 45. Factors ()));

}

{{out}}

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

#include <iomanip>

#include <vector>

return EXIT_SUCCESS;

{{out}}

=={{header|Ceylon}}==

{Integer*} getFactors(Integer n) =>

(1..n).filter((Integer element) => element.divides(n));

print("the factors of ``i`` are ``getFactors(i)``");

}

=={{header|Chapel}}==

Inspired by the Clojure solution:

for i in 1..floor(sqrt(n)):int {

if n % i == 0 then {

}

}

=={{header|Clojure}}==

(filter #(zero? (rem n %)) (range 1 (inc n))))

(1 3 5 9 15 45)

Improved version. Considers small factors from 1 up to (sqrt n) -- we increment it because range does not include the end point. Pair each small factor with its co-factor, flattening the results, and put them into a sorted set to get the factors in order.

(into (sorted-set)

(mapcat (fn [x] [x (/ n x)])

Same idea, using for comprehensions.

(into (sorted-set)

(reduce concat

(for [x (range 1 (inc (Math/sqrt n))) :when (zero? (rem n x))]

=={{header|CLU}}==

{{trans|Sather}}

x0: int := s/2

if x0=0 then return(s) end

stream$putl(po, "")

end

{{out}}

<pre>Factors of 3135: 1 3 1045 5 627 11 285 15 209 19 165 33 95 55 57 3135

=={{header|COBOL}}==

IDENTIFICATION DIVISION.

PROGRAM-ID. FACTORS.

END PROGRAM FACTORS.

=={{header|CoffeeScript}}==

# robust--we'll use it to verify the more complicated (but hopefully faster)

# algorithm.

console.log n, factors

if n < 1000000

{{out}}

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

We iterate in the range <code>1..sqrt(n)</code> collecting ‘low’ factors and corresponding ‘high’ factors, and combine at the end to produce an ordered list of factors.

(do ((limit (1+ (isqrt n))) (factor 1 (1+ factor)))

((= factor limit)

(when (zerop remainder)

(push factor lows)

=={{header|Crystal}}==

{{trans|Ruby}}

Brute force and slow, by checking every value up to n.

def factors() (1..self).select { |n| (self % n).zero? } end

Faster, by only checking values up to <math>\sqrt{n}</math>.

def factors

f = [] of Int32

f.sort

end

'''Tests:'''

{{out}}

<pre>

=={{header|D}}==

===Procedural Style===

T[] factors(T)(in T n) pure nothrow {

void main() {

writefln("%(%s\n%)", [45, 53, 64, 1111111].map!factors);

{{out}}

<pre>[1, 3, 5, 9, 15, 45]

===Functional Style===

auto factors(I)(I n) {

void main() {

36.factors.writeln;

{{out}}

<pre>[1, 2, 3, 4, 6, 9, 12, 18, 36]</pre>

=={{header|Dc}}==

=== Simple O(n) version ===

[Enter positive number: ]P ? sn

[Factors of ]P lnn [ are: ]P

[q]sq 1si [[ ]P lin]sp [ li ln <q ln li % 0=p li1+si lxx ]dsxx AP

{{out}}

Factors of 998877 are: 1 3 11 33 30269 90807 332959 998877

0m1.120s

=== Faster O(sqrt(n)) version ===

[Enter positive number: ]P ? sn

[Factors of ]P lnn [ are: ]P

[li lv <q ln li % 0=P li1+si lxx]dsxx

[lj 1>q lj1-sj Lbsi lpx lxx]dsxx AP

0m0.004s

=={{header|Delphi}}==

=={{header|Dyalect}}==

for x in this when pred(x) {

yield x

for x in 45.Factors() {

print(x)

Output:

=={{header|E}}==

{{improve|E|Use a cleverer algorithm such as in the Common Lisp example.}}

var xfactors := []

for f ? (x % f <=> 0) in 1..x {

}

return xfactors

=={{header|EasyLang}}==

for i = 1 to n

if n mod i = 0

.

.

=={{header|EchoLisp}}==

'''prime-factors''' gives the list of n's prime-factors. We mix them to get all the factors.

;; ppows

;; input : a list g of grouped prime factors ( 3 3 3 ..)

(for/fold (divs'(1)) ((g (map ppows (group (prime-factors n)))))

(for*/list ((a divs) (b g)) (* a b))))))

{{out}}

(lib 'bigint)

(factors 666)

(time ( length (factors huge)))

→ (394ms 7776)

=={{header|EDSAC order code}}==

2021-10-10 Integers are now read from the tape in decimal format, instead of being defined by the awkward method of pseudo-orders. The factorization of 999,999,999 has been removed, as it took too long on the commonly-used EdsacPC simulator (14.6 million orders - over 6 hours on the original EDSAC).

[Factors of an integer, from Rosetta Code website.]

[EDSAC program, Initial Orders 2.]

E 4 Z [define entry point]

P F [acc = 0 on entry]

{{out}}

<pre>

===Using higher-order function===

===Using comprehension===

=={{header|Elixir}}==

def factor(1), do: [1]

def factor(n) do

IO.puts "#{name}\t prime count : #{value},\t#{time/1000000} sec"

end)

{{out}}

=={{header|Erlang}}==

===with Built in fuctions===

===Recursive===

Another, less concise, but faster version

-module(divs).

divisors(K,N,_Q) ->

[K, N div K] ++ divisors(K+1,N,math:sqrt(N)).

{{out}}

<pre>

=={{header|ERRE}}==

PROGRAM FACTORS

PRINT("The factors of 12345 are ";L$)

END PROGRAM

{{out}}

<pre>

{{Works with|Office 365 Betas 2021}}

IF(1 < n,

LET(

IF(1 = n, {1}, NA())

)

and assuming that in the same worksheet, each of the following names is bound to the reusable generic lambda expression which follows it:

=LAMBDA(xs,

LAMBDA(ys,

)

)

The '''FACTORS''' function, applied to an integer, defines a column of integer values.

Also, this is lazily evaluated.

for divisor in 1 .. (float >> sqrt >> int) number do

if number % divisor = 0 then

yield divisor

if number <> 1 then yield number / divisor //special case condition: when number=1 then divisor=(number/divisor), so don't repeat it

===Prime factoring===

{{out}}

=={{header|FALSE}}==

=={{header|Fish}}==

>i:0(?v'0'%+a*

>~a,:1:>r{% ?vr:nr','ov

^:&:;?(&:+1r:< <

Must be called with pre-polulated value (Positive Integer) in the input stack. Try at Fish Playground[https://fishlanguage.com/playground/onD7KN6YK3XMzLFdr].

For Input Number : <pre> 120</pre>

=={{header|Forth}}==

This is a slightly optimized algorithm, since it realizes there are no factors between n/2 and n. The values are saved on the stack and - in true Forth fashion - printed in descending order.

: .factors factors begin dup dup . 1 <> while drop repeat drop cr ;

53 .factors

64 .factors

=== Alternative version with vectored execution ===

It's not really idiomatic FORTH to leave a variable number of items on the stack, so instead this version repeatedly calls an execution token for each factor, and it uses a defining word to create a fold over the factors of an integer. This version also only tests up to the square root, which means that items are generated in pairs, rather than in sorted order.

: sq s" dup *" evaluate ; immediate

0 :noname swap . ; <with-factors> (.factors)

: .factors (.factors) drop ;

{{Out}}

<pre>

=={{header|Fortran}}==

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

implicit none

integer :: i, number

end if

=={{header|FreeBASIC}}==

Sub printFactors(n As Integer)

Print

Print "Press any key to quit"

{{out}}

The following produces all factors of n, including 1 and n:

=={{header|FunL}}==

Function to compute set of factors:

Test:

{{out}}

=={{header|FutureBasic}}==

clear local mode

print @"Factors of 32434243 are:"; fn IntegerFactors( 32434243 )

Output:

=={{header|GAP}}==

DivisorsInt(Factorial(5));

# [ 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120 ]

div2(Factorial(5));

=={{header|Go}}==

Trial division, no prime number generator, but with some optimizations. It's good enough to factor any 64 bit integer, with large primes taking several seconds.

import "fmt"

fmt.Println(fs)

fmt.Println("Number of factors =", len(fs))

{{out}}

=={{header|Gosu}}==

numbers.each(\ number -> printFactors(number))

(1 .. n/2).each(\ i -> {result += n % i == 0 ? "${i} " : ""})

print("${result}${n}")

{{out}}

=={{header|Groovy}}==

A straight brute force approach up to the square root of ''N'':

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

[1] + lowfactors + (0..<nhalf).collect { target.intdiv(lowfactors[it]) }.reverse() + [target]

Test:

{{out}}

<pre>[number:1, factors:[1]]

=={{header|Haskell}}==

Using [https://web.archive.org/web/20121130222921/http://www.polyomino.f2s.com/david/haskell/codeindex.html D. Amos'es Primes module] for finding prime factors

import Control.Monad (mapM)

import Data.List (product)

factors = map product .

Returns list of factors out of order, e.g.:

<Lang haskell>~> factors 42

Or, [[Prime_decomposition#Haskell|prime decomposition task]] can be used (although, a trial division-only version will become very slow for large primes),

The above function can also be found in the package [http://hackage.haskell.org/package/arithmoi <code>arithmoi</code>], as <code>Math.NumberTheory.Primes.factorise :: Integer -> [(Integer, Int)]</code>, [http://hackage.haskell.org/package/arithmoi-0.4.2.0/docs/Math-NumberTheory-Primes-Factorisation.html which performs] "factorisation of Integers by the elliptic curve algorithm after Montgomery" and "is best suited for numbers of up to 50-60 digits".

Or, deriving cofactors from factors up to the square root:

integerFactors n

| 1 > n = []

main :: IO ()

{{Out}}

<pre>[1,2,3,4,5,6,8,10,12,15,20,24,25,30,40,50,60,75,100,120,150,200,300,600]</pre>

=== List comprehension ===

Naive, functional, no import, in increasing order:

[ i

| i <- [1 .. n]

Factor, ''cofactor''. Get the list of factor&ndash;cofactor pairs sorted, for a quadratic speedup:

factorsCo n =

i :

[ d

A version of the above without the need for sorting, making it to be ''online'' (i.e. productive immediately, which can be seen in GHCi); factors in increasing order:

ds ++

[ r

[ i

| i <- [1 .. r - 1]

Testing:

~> factorsO 120

[1,2,3,4,5,6,8,10,12,15,20,24,30,40,60,120]

[1,7,41,287,541,3787,22181,77551,155267,542857,3179591,22257137,41955091,2936856

37,1720158731,12041111117]

=={{header|HicEst}}==

DO i = 1, N^0.5

ENDDO

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

numbers := arglist ||| [ 32767, 45, 53, 64, 100] # combine command line provided and default set of values

every writes(lf,"factors of ",i := !numbers,"=") & writes(divisors(i)," ") do lf := "\n"

end

{{out}}

The "brute force" approach is the most concise:

Example use:

Basically we test every non-negative integer up through the number itself to see if it divides evenly.

J has a primitive, q: which returns its argument's prime factors.

Alternatively, q: can produce provide a table of the exponents of the unique relevant prime factors

2 3 5 7

With this, we can form lists of each of the potential relevant powers of each of these prime factors

┌─────┬───┬───┬───┐

│1 2 4│1 3│1 5│1 7│

From here, it's a simple matter (<code>*/&>@{</code> or, find all possible combinations of one item from each list (<code>{</code> without a left argument) then unpack each list and multiply its elements) to compute all possible factors of the original number

factrs 40

1 5

2 10

4 20

However, a data structure which is organized around the prime decomposition of the argument can be hard to read. So, for reader convenience, we should probably arrange them in a monotonically increasing list:

factors 420

A less efficient, but concise variation on this theme:

This computes 2^n intermediate values where n is the number of prime factors of the original number.

That said, note that we get a representation issue when dealing with large numbers:

One approach here (if we don't want to explicitly format the result) is to use an arbitrary precision (aka "extended") argument. This propagates through into the result:

Another less efficient approach, in which remainders are examined up to the square root, larger factors obtained as fractions, and the combined list nubbed and sorted might be:

Y=. y"_

/:~ ~. ( , Y%]) ( #~ 0=]|Y) 1+i.>.%:y

factorsOfNumber 40

Another approach:

See http://www.jsoftware.com/jwiki/Essays/Odometer

=={{header|Java}}==

{{works with|Java|5+}}

{

TreeSet<Long> factors = new TreeSet<Long>();

}

return factors;

=={{header|JavaScript}}==