Prime decomposition: Difference between revisions
(A lot of work went into this task description...) |
No edit summary |
||
| Line 18: | Line 18: | ||
return ans; |
return ans; |
||
} |
} |
||
=={{header|Lisp}}== |
|||
<pre> |
|||
(defun prime-decomposition (n) |
|||
(when (> n 1) |
|||
(loop for d from 2 upto n |
|||
until (zerop (mod n d)) |
|||
finally (return (cons d (prime-decomposition (truncate n d))))))) |
|||
</pre> |
|||
Revision as of 04:34, 5 February 2008
You are encouraged to solve this task according to the task description, using any language you may know.
The prime decomposition of a number is defined as a list of prime numbers which when all multiplied together, are equal to that number. Example: 12 = 2 * 2 * 3, so its prime decomposition is {2, 2, 3}
Write a function which returns an array or collection which contains the prime decomposition of a given number, n, greater than 1. If your language does not have an isPrime-like function available, you may assume that you have a function which determines whether a number is prime (note its name before your code).
If you would like to test code from this task, you may use code from prime numbers or the Sieve of Eratosthenes.
Java
A method which determines if a number is prime is assumed to be a boolean method called "prime" which takes in a double.
public static LinkedList<Long> primeFactor(double a){
LinkedList<Long> ans= new LinkedList<Long>();
for(double i= 2; i <= a && a != 1; i++){
if(prime(i) && a % i == 0){
ans.add(i);
a= a / i;
i= 1;
}
}
return ans;
}
Lisp
(defun prime-decomposition (n)
(when (> n 1)
(loop for d from 2 upto n
until (zerop (mod n d))
finally (return (cons d (prime-decomposition (truncate n d)))))))