Factors of an integer: Difference between revisions
(→Maxima: new example) |
(→{{header|Maxima}}: add note on implementing it) |
||
Line 174: | Line 174: | ||
<lang maxima>(%i96) divisors(100); |
<lang maxima>(%i96) divisors(100); |
||
(%o96) {1,2,4,5,10,20,25,50,100}</lang> |
(%o96) {1,2,4,5,10,20,25,50,100}</lang> |
||
<!-- Tried to write a reasonably elegant implementation; got these two versions which don't quite work |
|||
apply(outermap, append(["*"], map(lambda([fac], makelist(fac[1]^i, i, 0, fac[2])), ifactors(100)))); |
|||
Returns all factors, but as a nested list whose depth depends on the number of prime factors. |
|||
apply(cartesian_product, map(lambda([fac], setify(makelist(fac[1]^i, i, 0, fac[2]))), ifactors(100))); |
|||
Returns all factors in a set, but each factor is represented as a list of its prime factors. |
|||
—[[User:Kevin Reid]] 2009-12-26 --> |
|||
=={{header|Perl 6}}== |
=={{header|Perl 6}}== |
Revision as of 14:58, 26 December 2009
You are encouraged to solve this task according to the task description, using any language you may know.
Basic Data Operation
This is a basic data operation. It represents a fundamental action on a basic data type.
You may see other such operations in the Basic Data Operations category, or:
Integer Operations
Arithmetic |
Comparison
Boolean Operations
Bitwise |
Logical
String Operations
Concatenation |
Interpolation |
Comparison |
Matching
Memory Operations
Pointers & references |
Addresses
Compute the factors of a number. The factors of a positive integer are those positive integers by which it can be divided to yield a positive integer result (though the concepts function correctly for zero and negative integers, the set of factors of zero is has countably infinite members, and the factors of negative integers can be obtained from the factors of related positive numbers without difficulty; this task does not require handling of either of these cases). Note that even prime numbers will have at least two factors; ‘1’ and themselves.
See also:
AutoHotkey
<lang AutoHotkey>msgbox, % factors(45) "`n" factors(53) "`n" factors(64)
Factors(n) { Loop, % floor(sqrt(n))
{ v := A_Index = 1 ? 1 "," n : mod(n,A_Index) ? v : v "," A_Index "," n//A_Index } Sort, v, N U D, Return, v
}</lang>
Output: 1,3,5,9,15,45 1,53 1,2,4,8,16,32,64
Clojure
<lang lisp>(defn factors [n] (filter #(zero? (rem n %)) (range 1 (inc n))))
(print (factors 45))</lang>
(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.
<lang lisp>(defn factors [n]
(into (sorted-set) (mapcat (fn [x] [x (/ n x)]) (filter #(zero? (rem n %)) (range 1 (inc (sqrt n)))) )))</lang>
Same idea, using for comprehensions.
<lang lisp>(defn factors [n]
(into (sorted-set) (reduce concat (for [x (range 1 (inc (sqrt n))) :when (zero? (rem n x))] [x (/ n x)]))))</lang>
Common Lisp
We iterate in the range 1..sqrt(n)
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))) ((= factor limit) (when (= n (* limit limit)) (push limit highs)) (nreconc lows highs)) (multiple-value-bind (quotient remainder) (floor n factor) (when (zerop remainder) (push factor lows) (push quotient highs)))))</lang>
D
<lang d>int[]factors(int num) {
int[]ret; for(n=1;n<=num;n++) if (num%n==0) ret ~= n;
}</lang>
E
<lang e>def factors(x :(int > 0)) {
var xfactors := [] for f ? (x % f <=> 0) in 1..x { xfactors with= f } return xfactors
}</lang>
Erlang
<lang erlang>factors(N) ->
[I || I <- lists:seq(1,N div 2), N rem I == 0]++[N].</lang>
F#
<lang fsharp>let factors n = [for i in 1..n do if n%i=0 then yield i]</lang>
Haskell
Using D. Amos module Primes [1] for finding prime factors <lang Haskell> import HFM.Primes(primePowerFactors) import Data.List
factors = map product.
mapM (uncurry((. enumFromTo 0) . map .(^) )) . primePowerFactors
</lang>
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 3 1</lang>
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>
┌───────┬───┐ │1 2 4 8│1 5│ └───────┴───┘
From here, it's a simple matter to compute all possible factors of the original number
<lang J>factors=: */&>@{@((^ i.@>:)&.>/)@q:~&__</lang>
<lang J>factors 40
1 5 2 10 4 20 8 40</lang>
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 )</lang>
<lang J>factors 40 1 2 4 5 8 10 20 40</lang>
Java
<lang java5>public static TreeSet<Long> factors(long n){ TreeSet<Long> factors = new TreeSet<Long>(); factors.add(n); factors.add(1L); for(long test = n - 1; test >= Math.sqrt(n); test--){ if(n % test == 0){ factors.add(test); factors.add(n / test); } } return factors; }</lang>
JavaScript
<lang javascript>function factors(num) {
var factors = new Array(); var sqrt = Math.floor(Math.sqrt(num)); for (var i = 1; i <= sqrt; i++) { if (num % i == 0) { factors.push(i); if (num / i != i) factors.push(num / i); } } factors.sort(function(a,b){return a-b}); // numeric sort return factors;
}
factors(45); // [1,3,5,9,15,45] factors(53); // [1,53] factors(64); // [1,2,4,8,16,32,64] </lang>
Maxima
<lang maxima>(%i96) divisors(100); (%o96) {1,2,4,5,10,20,25,50,100}</lang>
Perl 6
<lang perl6>sub factors (Int $n) {
sort +*, keys hash map { $^x => 1, $n div $^x => 1 }, grep { $n !% $^x }, 1 .. ceiling sqrt $n;
}</lang>
PowerShell
Straightforward but slow
<lang powershell>function Get-Factor ($a) {
1..$a | Where-Object { $a % $_ -eq 0 }
}</lang>
This one uses a range of integers up to the target number and just filters it using the Where-Object
cmdlet. It's very slow though, so it is not very usable for larger numbers.
A little more clever
<lang powershell>function Get-Factor ($a) {
1..[Math]::Sqrt($a) ` | Where-Object { $a % $_ -eq 0 } ` | ForEach-Object { $_; $a / $_ } ` | Sort-Object -Unique
}</lang> Here the range of integers is only taken up to the square root of the number, the same filtering applies. Afterwards the corresponding larger factors are calculated and sent down the pipeline along with the small ones found earlier.
Perl
<lang perl>sub factors {
my($n) = @_; return grep { $n % $_ == 0 }(1 .. $n);
} print join ' ',factors(64);</lang>
Python
Naive and slow but simplest (check all numbers from 1 to n): <lang python>>>> def factors(n):
return [i for i in range(1, n + 1) if not n%i]</lang>
Slightly better (realize that there are no factors between n/2 and n): <lang python>>>> def factors(n):
return [i for i in range(1, n//2 + 1) if not n%i] + [n]
>>> factors(45) [1, 3, 5, 9, 15, 45]</lang>
Much better (realize that factors come in pairs, the smaller of which is no bigger than sqrt(n)): <lang python>>>> from math import ceil, sqrt >>> def factor(n):
return sorted(set(sum( ([x,n/x] for x in range(1, ceil(sqrt(n)) + 1) if not n%x), [] )))
>>> for i in (45, 53, 64): print( "%i: factors: %s" % (i, factor(i)) )
45: factors: [1, 3, 5, 9, 15, 45] 53: factors: [1, 53] 64: factors: [1, 2, 4, 8, 16, 32, 64]</lang>
R
<lang R> factors <- function(n) {
if(length(n) > 1) { lapply(as.list(n), factors) } else { one.to.n <- seq_len(n) one.to.n[(n %% one.to.n) == 0] }
} factors(60) </lang>
1 2 3 4 5 6 10 12 15 20 30 60
<lang R> factors(c(45, 53, 64)) </lang> <lang> 1 [1] 1 3 5 9 15 45 2 [1] 1 53 3 [1] 1 2 4 8 16 32 64 </lang>
Ruby
<lang ruby>class Integer
def factors() (1..self).select { |n| (self % n).zero? } end
end p 45.factors</lang>
[1, 3, 5, 9, 15, 45]
As we only have to loop up to , we can write <lang ruby>class Integer
def factors() 1.upto(Math.sqrt(self)).select {|i| (self % i).zero?}.inject([]) do |f, i| f << i f << self/i unless i == self/i f end.sort end
end [45, 53, 64].each {|n| p n.factors}</lang> output
[1, 3, 5, 9, 15, 45] [1, 53] [1, 2, 4, 8, 16, 32, 64]
Scala
<lang scala> def factor(n:Int) = (1 to Math.sqrt(n)).filter(n%_== 0).flatMap(x=>List(n/x,x)).toList.sort(_>_) </lang>
Scheme
This implementation uses a naive trial division algorithm. <lang scheme>(define (factors n)
(define (*factors d) (cond ((> d n) (list)) ((= (modulo n d) 0) (cons d (*factors (+ d 1)))) (else (*factors (+ d 1))))) (*factors 1))
(display (factors 1111111)) (newline)</lang> Output:
(1 239 4649 1111111)
Slate
<lang slate> n@(Integer traits) primeFactors [
[| :result | result nextPut: 1. n primesDo: [| :prime | result nextPut: prime]] writingAs: {}
]. </lang> where primesDo: 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)." [| div next remaining |
div: 2. next: 3. remaining: n. [[(remaining \\ div) isZero] whileTrue: [block applyTo: {div}.
remaining: remaining // div].
remaining = 1] whileFalse: [div: next. next: next + 2] "Just looks at the next odd integer."
]. </lang>
Tcl
<lang tcl>proc factors {n} {
set factors {} for {set i 1} {$i <= sqrt($n)} {incr i} { if {$n % $i == 0} { lappend factors $i [expr {$n / $i}] } } return [lsort -unique -integer $factors]
} puts [factors 64] puts [factors 45] puts [factors 53]</lang> output
1 2 4 8 16 32 64 1 3 5 9 15 45 1 53
Ursala
Filter the sequence of numbers from 1 to n according to divisibility into n. <lang Ursala>
- import std
- import nat
factors "n" = (not remainder/"n")*~@t iota successor "n" </lang> test program: <lang Ursala>
- cast %nL
example = factors 100 </lang> output:
<1,2,4,5,10,20,25,50,100>