Anonymous user
Factors of an integer: Difference between revisions
m
whitespace
(→{{header|Mercury}}: Eliminated the need for checks on bad arguments.) |
m (whitespace) |
||
Line 17:
=={{header|Ada}}==
<lang Ada>with Ada.Text_IO;
with Ada.Command_Line;
Line 42 ⟶ 41:
=={{header|Aikido}}==
<lang aikido>import math
function factor (n:int) {
Line 76 ⟶ 74:
printvec (factor (45))
printvec (factor (25))
printvec (factor (100))</lang>
=={{header|ALGOL 68}}==
Line 122 ⟶ 117:
=={{header|AutoHotkey}}==
<lang AutoHotkey>msgbox, % factors(45) "`n" factors(53) "`n" factors(64)
Line 151 ⟶ 145:
Next
Return $ls_factors&$intg
EndFunc</lang>
<pre>
Output:
Line 160 ⟶ 153:
=={{header|BASIC}}==
{{works with|QBasic}}
This example stores the factors in a shared array (with the original number as the last element) for later retrieval.
Note that this will error out if you pass 32767 (or higher).
<lang qbasic>DECLARE SUB factor (what AS INTEGER)
Line 249 ⟶ 239:
Interactive version:
<lang dos>@echo off
set /p limit=Gimme a number:
Line 297 ⟶ 286:
L$ += STR$(L%(I%)) + ", "
NEXT
= LEFT$(LEFT$(L$))</lang>
Output:
<pre>The factors of 45 are 1, 3, 5, 9, 15, 45
Line 524 ⟶ 512:
Console.WriteLine(String.Join(", ", 45.Factors()));
}
}</lang>
C# 1.0
<lang csharp>static void Main(string[] args)
{
Line 556 ⟶ 542:
Console.WriteLine("Done.");
} while (true);
}</lang>
Example output:
Line 568 ⟶ 553:
=={{header|Clojure}}==
<lang lisp>(defn factors [n]
(filter #(zero? (rem n %)) (range 1 (inc n))))
Line 576 ⟶ 560:
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.
<lang lisp>(defn factors [n]
(into (sorted-set)
Line 583 ⟶ 566:
Same idea, using for comprehensions.
<lang lisp>(defn factors [n]
(into (sorted-set)
Line 591 ⟶ 573:
=={{header|CoffeeScript}}==
<lang coffeescript># Reference implementation for finding factors is slow, but hopefully
# robust--we'll use it to verify the more complicated (but hopefully faster)
# algorithm.
Line 650 ⟶ 631:
console.log n, factors
if n < 1000000
verify_factors factors, n</lang>
output
<lang coffeescript>> coffee factors.coffee
1 [ 1 ]
3 [ 1, 3 ]
Line 674 ⟶ 653:
11111111111,
33333333333,
99999999999 ]</lang>
=={{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.
<lang lisp>(defun factors (n &aux (lows '()) (highs '()))
(do ((limit (isqrt n)) (factor 1 (1+ factor)))
Line 723 ⟶ 698:
[1, 239, 4649, 1111111]</pre>
Functional style:
<lang d>import std.stdio, std.algorithm, std.range;
Line 737 ⟶ 711:
=={{header|E}}==
{{improve|E|Use a cleverer algorithm such as in the Common Lisp example.}}
<lang e>def factors(x :(int > 0)) {
var xfactors := []
Line 747 ⟶ 719:
return xfactors
}</lang>
=={{header|Ela}}==
===Using higher-order function===
<lang ela>open Core
Line 758 ⟶ 728:
===Using comprehension===
<lang ela>let factors m = [x \\ x <- [1..m] | m % x == 0]</lang>
Line 796 ⟶ 765:
64 .factors
100 .factors</lang>
=={{Header|Fortran}}==
Line 820 ⟶ 788:
end program</lang>
=={{header|GAP}}==
<lang gap># Built-in function
Line 841 ⟶ 810:
div2(Factorial(5));
# [ 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120 ]</lang>
=={{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.
Line 942 ⟶ 912:
Test:
<lang groovy>((1..30) + [333333]).each { println ([number:it, factors:factorize(it)]) }</lang>
Output:
<pre>[number:1, factors:[1]]
Line 978 ⟶ 947:
=={{Header|Haskell}}==
Using D. Amos module Primes [http://www.polyomino.f2s.com/david/haskell/codeindex.html] for finding prime factors
<lang Haskell>import HFM.Primes(primePowerFactors)
import Data.List
factors = map product.
mapM (uncurry((. enumFromTo 0) . map .(^) )) . primePowerFactors</lang>
=={{header|HicEst}}==
Line 1,012 ⟶ 979:
=={{header|J}}==
J has a primitive, q: which returns its prime factors.
<lang J>q: 40
2 2 2 5</lang>
Alternatively, q: can produce provide a table of the exponents of the unique relevant prime factors
<lang J>__ q: 40
2 5
Line 1,025 ⟶ 989:
With this, we can form lists of each of the potential relevant powers of each of these prime factors
<lang J>((^ i.@>:)&.>/) __ q: 40</lang>
┌───────┬───┐
Line 1,032 ⟶ 995:
From here, it's a simple matter (<code>*/&>@{</code>) to compute all possible factors of the original number
<lang J>factors=: */&>@{@((^ i.@>:)&.>/)@q:~&__</lang>
Line 1,042 ⟶ 1,004:
A 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:
<lang J>factors=: monad define
Y=. y"_
/:~ ~. ( , Y%]) ( #~ 0=]|Y) 1+i.>.%:y
Line 1,113 ⟶ 1,073:
/ Number of factors for 3491888400 .. 3491888409
#:'f' 3491888400+!10
1920 16 4 4 12 16 32 16 8 24</lang>
=={{header|Liberty BASIC}}==
<lang lb>num = 10677106534462215678539721403561279
maxnFactors = 1000
dim primeFactors(maxnFactors), nPrimeFactors(maxnFactors)
Line 1,190 ⟶ 1,148:
next i
end if
end function</lang>
Outcome:
<lang lb>Start finding all factors of 10677106534462215678539721403561279:
10677106534462215678539721403561279 = 29269^1 * 32579^1 * 98731^2 * 104729^3
1 1
Line 1,247 ⟶ 1,201:
47 364792324112959639158827476291
48 10677106534462215678539721403561279
done</lang>
=={{header|Logo}}==
Line 1,257 ⟶ 1,209:
show factors 28 ; [1 2 4 7 14 28]</lang>
=={{header|Lua}}==
<lang lua>function Factors( n )
Line 1,273 ⟶ 1,226:
=={{header|Mathematica}}==
<lang Mathematica>Factorize[n_Integer] := Divisors[n]</lang>
=={{header|MATLAB}} / {{header|Octave}}==
<lang Matlab> function fact(n);
f = factor(n); % prime decomposition
Line 1,307 ⟶ 1,258:
=={{header|Maxima}}==
The builtin <code>divisors</code> function does this.
<lang maxima>(%i96) divisors(100);
(%o96) {1,2,4,5,10,20,25,50,100}</lang>
Such a function could be implemented like so:
<lang maxima>divisors2(n) := map( lambda([l], lreduce("*", l)),
apply( cartesian_product,
Line 1,393 ⟶ 1,341:
=={{header|Niue}}==
<lang Niue>[ 'n ; [ negative-or-zero [ , ] if
[ n not-factor [ , ] when ] else ] n times n ] 'factors ;
Line 1,405 ⟶ 1,351:
53 factors .s .clr ( => 1 53 ) newline
64 factors .s .clr ( => 1 2 4 8 16 32 64 ) newline
12 factors .s .clr ( => 1 2 3 4 6 12 ) </lang>
=={{header|Objeck}}==
<lang objeck>use IO;
use Structure;
Line 1,447 ⟶ 1,391:
}
}
}</lang>
=={{header|OCaml}}==
Line 1,482 ⟶ 1,425:
=={{header|Pascal}}==
<lang pascal>program Factors;
var
Line 1,522 ⟶ 1,465:
=={{header|Perl 6}}==
{{works with|Rakudo Star|2010-08}}
<lang perl6>sub factors (Int $n) {
sort +*, keys hash
Line 1,531 ⟶ 1,473:
=={{header|PHP}}==
<lang PHP>function GetFactors($n){
$factors = array(1, $n);
for($i = 2; $i * $i <= $n; $i++){
Line 1,552 ⟶ 1,493:
=={{header|PL/I}}==
<lang PL/I>do i = 1 to n;
if mod(n, i) = 0 then put skip list (i);
end;</lang>
=={{header|PowerShell}}==
Line 1,605 ⟶ 1,544:
;
sort(LC, L)
).</lang>
Output :
<pre> ?- factor(36, L).
Line 1,677 ⟶ 1,615:
64: factors: [1, 2, 4, 8, 16, 32, 64]</lang>
More efficient when factoring many numbers
<lang python>def factor(n):
a, r = 1, [1]
while a * a < n:
Line 1,692 ⟶ 1,631:
=={{header|R}}==
<lang R>factors <- function(n)
{
if(length(n) > 1)
Line 1,704 ⟶ 1,642:
}
}
factors(60)</lang>
1 2 3 4 5 6 10 12 15 20 30 60
<lang R>factors(c(45, 53, 64))</lang>
<pre>
[[1]]
Line 1,735 ⟶ 1,670:
=={{header|REXX}}==
<lang rexx>/*REXX program to calculate & show divisors of positive integer(s). */
parse arg low high .; if high=='' then high=low
Line 1,769 ⟶ 1,703:
else p.2=arg(k) p.2 /*build (descending) to "high" list.*/
end
return</lang>
Below is the output for the divisors for the first two hundred integers
when
<
1 200
<
is entred as arguments.
<pre style="height:30ex;overflow:scroll">
Line 1,981 ⟶ 1,914:
=={{header|Ruby}}==
<lang ruby>class Integer
def factors() (1..self).select { |n| (self % n).zero? } end
Line 2,037 ⟶ 1,969:
=={{header|Scala}}==
<lang scala>def factor(n:Int) = (1 to Math.sqrt(n)).filter(n%_== 0).flatMap(x=>List(n/x,x)).toList.sort(_>_)</lang>
=={{header|Scheme}}==
Line 2,056 ⟶ 1,986:
=={{header|Slate}}==
<lang slate>n@(Integer traits) primeFactors
[
[| :result |
result nextPut: 1.
n primesDo: [| :prime | result nextPut: prime]] writingAs: {}
].</lang>
where <tt>primesDo:</tt> is a part of the standard numerics library:
<lang slate>n@(Integer traits) primesDo: block
"Decomposes the Integer into primes, applying the block to each (in increasing
order)."
Line 2,080 ⟶ 2,007:
[div: next.
next: next + 2] "Just looks at the next odd integer."
].</lang>
=={{header|Tcl}}==
|