Factors of an integer: Difference between revisions
No edit summary |
|||
Line 627: | Line 627: | ||
64 factors .s .clr ( => 1 2 4 8 16 32 64 ) newline |
64 factors .s .clr ( => 1 2 4 8 16 32 64 ) newline |
||
12 factors .s .clr ( => 1 2 3 4 6 12 ) |
12 factors .s .clr ( => 1 2 3 4 6 12 ) |
||
</lang> |
|||
=={{header|Objeck}}== |
|||
<lang objeck> |
|||
use IO; |
|||
use Structure; |
|||
bundle Default { |
|||
class Basic { |
|||
function : native : GenerateFactors(n : Int) ~ IntVector { |
|||
factors := IntVector->New(); |
|||
factors-> AddBack(1); |
|||
factors->AddBack(n); |
|||
for(i := 2; i * i <= n; i += 1;) { |
|||
if(n % i = 0) { |
|||
factors->AddBack(i); |
|||
if(i * i <> n) { |
|||
factors->AddBack(n / i); |
|||
}; |
|||
}; |
|||
}; |
|||
factors->Sort(); |
|||
return factors; |
|||
} |
|||
function : Main(args : String[]) ~ Nil { |
|||
numbers := [3135, 45, 60, 81]; |
|||
for(i := 0; i < numbers->Size(); i += 1;) { |
|||
factors := GenerateFactors(numbers[i]); |
|||
Console->GetInstance()->Print("Factors of ")->Print(numbers[i])->PrintLine(" are:"); |
|||
each(i : factors) { |
|||
Console->GetInstance()->Print(factors->Get(i))->Print(", "); |
|||
}; |
|||
"\n\n"->Print(); |
|||
}; |
|||
} |
|||
} |
|||
} |
|||
</lang> |
</lang> |
||
Revision as of 20:19, 22 August 2010
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
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:
ActionScript
<lang ActionScript>function factor(n:uint):Vector.<uint> { var factors:Vector.<uint> = new Vector.<uint>(); for(var i:uint = 1; i <= n; i++) if(n % i == 0)factors.push(i); return factors; }</lang>
Aikido
<lang aikido> import math
function factor (n:int) {
var result = [] function append (v) { if (!(v in result)) { result.append (v) } } var sqrt = cast<int>(Math.sqrt (n)) append (1) for (var i = n-1 ; i >= sqrt ; i--) { if ((n % i) == 0) { append (i) append (n/i) } } append (n) return result.sort()
}
function printvec (vec) {
var comma = "" print ("[") foreach v vec { print (comma + v) comma = ", " } println ("]")
}
printvec (factor (45)) printvec (factor (25)) printvec (factor (100))
</lang>
ALGOL 68
Note: The following implements generators, eliminating the need of declaring arbitrarily long int arrays for caching. <lang algol68>MODE YIELDINT = PROC(INT)VOID;
PROC gen factors = (INT n, YIELDINT yield)VOID: (
FOR i FROM 1 TO ENTIER sqrt(n) DO IF n MOD i = 0 THEN yield(i); INT other = n OVER i; IF i NE other THEN yield(n OVER i) FI FI OD
);
[]INT nums2factor = (45, 53, 64);
FOR i TO UPB nums2factor DO
INT num = nums2factor[i]; STRING sep := ": "; print(num);
- FOR INT j IN # gen factors(num, # ) DO ( #
- (INT j)VOID:(
print((sep,whole(j,0))); sep:=", "
- OD # ));
print(new line)
OD</lang> Output:
+45: 1, 45, 3, 15, 5, 9 +53: 1, 53 +64: 1, 64, 2, 32, 4, 16, 8
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
Batch File
Command line version: <lang dos>@echo off set res=Factors of %1: for /L %%i in (1,1,%1) do call :fac %1 %%i echo %res% goto :eof
- fac
set /a test = %1 %% %2 if %test% equ 0 set res=%res% %2</lang>
Outputs:
>factors 32767 Factors of 32767: 1 7 31 151 217 1057 4681 32767 >factors 45 Factors of 45: 1 3 5 9 15 45 >factors 53 Factors of 53: 1 53 >factors 64 Factors of 64: 1 2 4 8 16 32 64 >factors 100 Factors of 100: 1 2 4 5 10 20 25 50 100
Interactive version:
<lang dos>@echo off set /p limit=Gimme a number: set res=Factors of %limit%: for /L %%i in (1,1,%limit%) do call :fac %limit% %%i echo %res% goto :eof
- fac
set /a test = %1 %% %2 if %test% equ 0 set res=%res% %2</lang>
Outputs:
>factors Gimme a number:27 Factors of 27: 1 3 9 27 >factors Gimme a number:102 Factors of 102: 1 2 3 6 17 34 51 102
BASIC
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)
REDIM SHARED factors(0) AS INTEGER
DIM i AS INTEGER, L AS INTEGER
INPUT "Gimme a number"; i
factor i
PRINT factors(0); FOR L = 1 TO UBOUND(factors)
PRINT ","; factors(L);
NEXT PRINT
SUB factor (what AS INTEGER)
DIM tmpint1 AS INTEGER DIM L0 AS INTEGER, L1 AS INTEGER
REDIM tmp(0) AS INTEGER REDIM factors(0) AS INTEGER factors(0) = 1
FOR L0 = 2 TO what IF (0 = (what MOD L0)) THEN 'all this REDIMing and copying can be replaced with: 'REDIM PRESERVE factors(UBOUND(factors)+1) 'in languages that support the PRESERVE keyword REDIM tmp(UBOUND(factors)) AS INTEGER FOR L1 = 0 TO UBOUND(factors) tmp(L1) = factors(L1) NEXT REDIM factors(UBOUND(factors) + 1) FOR L1 = 0 TO UBOUND(factors) - 1 factors(L1) = tmp(L1) NEXT factors(UBOUND(factors)) = L0 END IF NEXT
END SUB</lang>
Sample outputs:
Gimme a number? 17 1 , 17 Gimme a number? 12345 1 , 3 , 5 , 15 , 823 , 2469 , 4115 , 12345 Gimme a number? 32765 1 , 5 , 6553 , 32765 Gimme a number? 32766 1 , 2 , 3 , 6 , 43 , 86 , 127 , 129 , 254 , 258 , 381 , 762 , 5461 , 10922 , 16383 , 32766
C
<lang c>#include <stdio.h>
- include <stdlib.h>
typedef struct {
int *list; short count;
} Factors;
void xferFactors( Factors *fctrs, int *flist, int flix ) {
int ix, ij; int newSize = fctrs->count + flix; if (newSize > flix) { fctrs->list = realloc( fctrs->list, newSize * sizeof(int)); } else { fctrs->list = malloc( newSize * sizeof(int)); } for (ij=0,ix=fctrs->count; ix<newSize; ij++,ix++) { fctrs->list[ix] = flist[ij]; } fctrs->count = newSize;
}
Factors *factor( int num, Factors *fctrs) {
int flist[301], flix; int dvsr; flix = 0; fctrs->count = 0; if (fctrs->list) free(fctrs->list); fctrs->list = NULL; for (dvsr=1; dvsr*dvsr < num; dvsr++) { if (num % dvsr != 0) continue; if ( flix == 300) { xferFactors( fctrs, flist, flix ); flix = 0; } flist[flix++] = dvsr; flist[flix++] = num/dvsr; } if (dvsr*dvsr == num) flist[flix++] = dvsr; if (flix > 0) xferFactors( fctrs, flist, flix );
return fctrs;
}
int main(int argc, char*argv[]) {
int nums2factor[] = { 2059, 223092870, 3135, 45 }; Factors ftors = { NULL, 0}; char sep; int i,j;
for (i=0; i<4; i++) { factor( nums2factor[i], &ftors ); printf("\nfactors of %d are:\n ", nums2factor[i]); sep = ' '; for (j=0; j<ftors.count; j++) { printf("%c %d", sep, ftors.list[j]); sep = ','; } printf("\n"); } return 0;
}</lang>
C++
<lang Cpp>#include <iostream>
- include <vector>
- include <algorithm>
std::vector<int> GenerateFactors(int n) {
std::vector<int> factors; factors.push_back(1); factors.push_back(n); for(int i = 2; i * i <= n; ++i) { if(n % i == 0) { factors.push_back(i); if(i * i != n) factors.push_back(n / i); } }
std::sort(factors.begin(), factors.end()); return factors;
}
int main() {
const int SampleNumbers[] = {3135, 45, 60, 81};
for(size_t i = 0; i < sizeof(SampleNumbers) / sizeof(int); ++i) { std::vector<int> factors = GenerateFactors(SampleNumbers[i]); std::cout << "Factors of " << SampleNumbers[i] << " are:\n"; std::copy(factors.begin(), factors.end(), std::ostream_iterator<int>(std::cout, "\n")); std::cout << std::endl; }
}</lang>
C#
C# 3.0 <lang csharp>using System; using System.Linq; using System.Collections.Generic;
public static class Extension {
public static List<int> Factors(this int me) { return Enumerable.Range(1, me).Where(x => me % x == 0).ToList(); }
}
class Program {
static void Main(string[] args) { Console.WriteLine(String.Join(", ", 45.Factors())); }
} </lang>
C# 1.0
<lang csharp>static void Main(string[] args) { do { Console.WriteLine("Number:"); Int64 p = 0; do { try { p = Convert.ToInt64(Console.ReadLine()); break; } catch (Exception) { }
} while (true);
Console.WriteLine("For 1 through " + ((int)Math.Sqrt(p)).ToString() + ""); for (int x = 1; x <= (int)Math.Sqrt(p); x++) { if (p % x == 0) Console.WriteLine("Found: " + x.ToString() + ". " + p.ToString() + " / " + x.ToString() + " = " + (p / x).ToString()); }
Console.WriteLine("Done."); } while (true); } </lang>
Example output:
Number: 32434243 For 1 through 5695 Found: 1. 32434243 / 1 = 32434243 Found: 307. 32434243 / 307 = 105649 Done.
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>import std.stdio ;
T[] factor(T)(T n) {
bool[T] result ; for(T i = 1 ; i*i <= n ; i++) if (n % i == 0) { result[i] = true ; result[n/i] = true ; } return result.keys.sort ;
}
void main() {
foreach(i ; [45, 53, 64, 1111111]) writefln("%s", factor(i)) ;
}</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>
Factor
USE: math.primes.factors ( scratchpad ) 24 divisors . { 1 2 3 4 6 8 12 24 }
FALSE
<lang false>[1[\$@$@-][\$@$@$@$@\/*=[$." "]?1+]#.%]f: 45f;! 53f;! 64f;!</lang>
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. <lang Forth>: factors dup 2/ 1+ 1 do dup i mod 0= if i swap then loop ;
- .factors factors begin dup dup . 1 <> while drop repeat drop cr ;
45 .factors 53 .factors 64 .factors 100 .factors</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>
HicEst
<lang hicest> DLG(NameEdit=N, TItle='Enter an integer')
DO i = 1, N^0.5 IF( MOD(N,i) == 0) WRITE() i, N/i ENDDO
END</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>
Mathematica
<lang Mathematica>Factorize[n_Integer] := Divisors[n]</lang>
Maxima
The builtin divisors
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, map( lambda([fac], setify(makelist(fac[1]^i, i, 0, fac[2]))), ifactors(n))));</lang>
MUMPS
<lang MUMPS>factors(num) New fctr,list,sep,sqrt If num<1 Quit "Too small a number" If num["." Quit "Not an integer" Set sqrt=num**0.5\1 For fctr=1:1:sqrt Set:num/fctr'["." list(fctr)=1,list(num/fctr)=1 Set (list,fctr)="",sep="[" For Set fctr=$Order(list(fctr)) Quit:fctr="" Set list=list_sep_fctr,sep="," Quit list_"]"
w $$factors(45) ; [1,3,5,9,15,45] w $$factors(53) ; [1,53] w $$factors(64) ; [1,2,4,8,16,32,64]</lang>
Niue
<lang Niue> [ 'n ; [ negative-or-zero [ , ] if
[ n not-factor [ , ] when ] else ] n times n ] 'factors ;
[ dup 0 <= ] 'negative-or-zero ; [ swap dup rot swap mod 0 = not ] 'not-factor ;
( tests ) 100 factors .s .clr ( => 1 2 4 5 10 20 25 50 100 ) newline 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>
Objeck
<lang objeck> use IO; use Structure;
bundle Default {
class Basic { function : native : GenerateFactors(n : Int) ~ IntVector { factors := IntVector->New(); factors-> AddBack(1); factors->AddBack(n);
for(i := 2; i * i <= n; i += 1;) { if(n % i = 0) { factors->AddBack(i); if(i * i <> n) { factors->AddBack(n / i); }; }; }; factors->Sort();
return factors; } function : Main(args : String[]) ~ Nil { numbers := [3135, 45, 60, 81]; for(i := 0; i < numbers->Size(); i += 1;) { factors := GenerateFactors(numbers[i]); Console->GetInstance()->Print("Factors of ")->Print(numbers[i])->PrintLine(" are:"); each(i : factors) { Console->GetInstance()->Print(factors->Get(i))->Print(", "); }; "\n\n"->Print(); }; } }
} </lang>
OCaml
<lang ocaml>let rec range = function 0 -> [] | n -> range(n-1) @ [n]
let factors n =
List.filter (fun v -> (n mod v) = 0) (range n)</lang>
Oz
<lang oz>declare
fun {Factors N} Sqr = {Float.toInt {Sqrt {Int.toFloat N}}} Fs = for X in 1..Sqr append:App do if N mod X == 0 then CoFactor = N div X in if CoFactor == X then %% avoid duplicate factor {App [X]} %% when N is a square number else {App [X CoFactor]} end end end in {Sort Fs Value.'<'} end
in
{Show {Factors 53}}</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>
PL/I
<lang PL/I> do i = 1 to n;
if mod(n, i) = 0 then put skip list (i);
end; </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>
PicoLisp
<lang PicoLisp>(de factors (N)
(filter '((D) (=0 (% N D))) (range 1 N) ) )</lang>
PureBasic
<lang PureBasic>Procedure PrintFactors(n)
Protected i, lim=Round(sqr(n),#PB_Round_Up) NewList F.i() For i=1 To lim If n%i=0 AddElement(F()): F()=i AddElement(F()): F()=n/i EndIf Next ;- Present the result SortList(F(),#PB_Sort_Ascending) ForEach F() Print(str(F())+" ") Next
EndProcedure
If OpenConsole()
Print("Enter integer to factorize: ") PrintFactors(Val(Input())) Print(#CRLF$+#CRLF$+"Press ENTER to quit."): Input()
EndIf</lang> Output can look like
Enter integer to factorize: 96 1 2 3 4 6 8 12 16 24 32 48 96
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]
Sather
<lang sather>class MAIN is
factors(n :INT):ARRAY{INT} is f:ARRAY{INT}; f := #; f := f.append(|1|); f := f.append(|n|); loop i ::= 2.upto!( n.flt.sqrt.int ); if n%i = 0 then f := f.append(|i|);
if (i*i) /= n then f := f.append(|n / i|); end;
end; end; f.sort; return f; end;
main is a :ARRAY{INT} := |3135, 45, 64, 53, 45, 81|; loop l ::= a.elt!; #OUT + "factors of " + l + ": "; r ::= factors(l); loop ri ::= r.elt!; #OUT + ri + " "; end; #OUT + "\n"; end; end;
end;</lang>
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
The simple way: <lang Ursala>#import std
- import nat
factors "n" = (filter not remainder/"n") nrange(1,"n")</lang>
The complicated way:
<lang Ursala>factors "n" = nleq-<&@s <.~&r,quotient>*= "n"-* (not remainder/"n")*~ nrange(1,root("n",2))</lang>
Another idea would be to approximate an upper bound for the square root of "n"
with some bit twiddling such as &!*K31 "n"
, which evaluates to a binary number of all 1's half the width of "n" rounded up, and another would be to use the division
function to get the quotient and remainder at the same time. Combining these ideas, losing the dummy variable, and cleaning up some other cruft, we have
<lang Ursala>factors = nleq-<&@rrZPFLs+ ^(~&r,division)^*D/~& nrange/1+ &!*K31</lang>
where nleq-<&
isn't strictly necessary unless an ordered list is required.
<lang Ursala>#cast %nL
example = factors 100</lang> output:
<1,2,4,5,10,20,25,50,100>
- Programming Tasks
- Basic language learning
- Basic Data Operations
- Arithmetic operations
- Mathematical operations
- ActionScript
- Aikido
- ALGOL 68
- AutoHotkey
- Batch File
- BASIC
- C
- C++
- C sharp
- Clojure
- Common Lisp
- D
- E
- E examples needing attention
- Examples needing attention
- Erlang
- F Sharp
- Factor
- FALSE
- Forth
- Haskell
- HicEst
- J
- Java
- JavaScript
- Mathematica
- Maxima
- MUMPS
- Niue
- Objeck
- OCaml
- Oz
- Perl 6
- PL/I
- PowerShell
- Perl
- PicoLisp
- PureBasic
- Python
- R
- Ruby
- Sather
- Scala
- Scheme
- Slate
- Tcl
- Ursala