Factors of an integer: Difference between revisions

From Rosetta Code
Content added Content deleted
Line 53: Line 53:
With this, we can form lists of each of the potential relevant powers of each of these prime factors
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 J>((^ i.@>:)&.>/) __ q: 40</lang>
┌───────┬───┐
┌───────┬───┐
│1 2 4 8│1 5│
│1 2 4 8│1 5│
└───────┴───┘</lang>
└───────┴───┘


From here, it's a simple matter to compute all possible factors of the original number
From here, it's a simple matter to compute all possible factors of the original number

Revision as of 15:37, 28 August 2009

Task
Factors of an integer
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:

Clojure

This example is incorrect. Please fix the code and remove this message.

Details: It needs to include the number itself in the list of factors; right now it is only producing the proper divisors of the number, which is not quite right.

<lang lisp>(defn factors [n] (filter #(zero? (rem n %)) (range 1 n)))

(print (factors 45))</lang>

(1 3 5 9 15)

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>

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>

Java

Works with: Java version 1.5+

<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>

Python

<lang python>>>> def factors(n): return [i for i in range(1,n//2) if not n%i] + [n]

>>> factors(45) [1, 3, 5, 9, 15, 45]</lang>

Alternative (after Ruby): <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]

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 by n. <lang Ursala>

  1. import std
  2. import nat

factors "n" = (not remainder/"n")*~@t iota successor "n" </lang> test program: <lang Ursala>

  1. cast %nL

example = factors 100 </lang> output:

<1,2,4,5,10,20,25,50,100>