Perfect numbers: Difference between revisions
(→{{header|MAXScript}}: remove redundant if) |
(added scheme) |
||
Line 248: | Line 248: | ||
n == (1..n-1).select {|i| n % i == 0}.inject(0) {|sum, i| sum + i} |
n == (1..n-1).select {|i| n % i == 0}.inject(0) {|sum, i| sum + i} |
||
end</ruby> |
end</ruby> |
||
=={{header|Scheme}}== |
|||
<scheme>(define (perf n) |
|||
(let loop ((i 1) |
|||
(sum 0)) |
|||
(cond ((= i n) |
|||
(= sum n)) |
|||
((= 0 (modulo n i)) |
|||
(loop (+ i 1) (+ sum i))) |
|||
(else |
|||
(loop (+ i 1) sum)))))</scheme> |
Revision as of 08:59, 11 December 2008
You are encouraged to solve this task according to the task description, using any language you may know.
Write a function which says whether a number is perfect.
A number is perfect if the sum of its factors is equal to twice the number. An equivalent condition is that n is perfect if the sum of n's factors that are less than n is equal to n.
Note: The faster Lucas-Lehmer_test is used to find primes of the form 2ⁿ-1, all known perfect numbers can derived from these primes using the formula (2n - 1) × 2n - 1. It is not known if there are any odd perfect numbers.
Ada
<Ada> function Is_Perfect(N : Positive) return Boolean is
Sum : Natural := 0;
begin
for I in 1..N - 1 loop if N mod I = 0 then Sum := Sum + I; end if; end loop; return Sum = N;
end Is_Perfect; </Ada>
ALGOL 68
PROC is perfect = (INT candidate)BOOL: ( INT sum :=1; FOR f1 FROM 2 TO ENTIER ( sqrt(candidate)*(1+2*small real) ) WHILE IF candidate MOD f1 = 0 THEN sum +:= f1; INT f2 = candidate OVER f1; IF f2 > f1 THEN sum +:= f2 FI FI; # WHILE # sum <= candidate DO SKIP OD; sum=candidate ); # test # FOR i FROM 2 TO 33550336 DO IF is perfect(i) THEN print((i, new line)) FI OD
Output:
+6 +28 +496 +8128 +33550336
BASIC
<qbasic>FUNCTION perf(n) sum = 0 for i = 1 to n - 1 IF n MOD i = 0 THEN sum = sum + i END IF NEXT i IF sum = n THEN perf = 1 ELSE perf = 0 END IF END FUNCTION</qbasic>
C
Based on the D version, for GCC: <c>
- include "stdio.h"
- include "math.h"
int perfect(int n) {
int max = (int)sqrt((double)n) + 1; int tot = 1; int i;
for (i = 2; i < max; i++) if (__builtin_expect((n % i) == 0, 1)) { tot += i; int q = n / i; if (q > i) tot += q; }
return tot == n;
}
int main() {
int n; for (n = 2; n < 33550337; n++) if (perfect(n)) printf("%d\n", n);
return 0;
} </c>
D
Based on the Algol version: <d> import std.math: sqrt;
bool perfect(int n) {
if (n < 2) return false; int max = cast(int)sqrt(cast(real)n) + 1; int tot = 1;
for (int i = 2; i < max; i++) if (n % i == 0) { tot += i; int q = n / i; if (q > i) tot += q; }
return tot == n;
}
void main() {
for (int n; n < 33_550_337; n++) if (perfect(n)) printf("%d\n", n);
} </d>
Forth
: perfect? ( n -- ? ) 1 over 2/ 1+ 2 ?do over i mod 0= if i + then loop = ;
Fortran
FUNCTION isPerfect(n) LOGICAL :: isPerfect INTEGER, INTENT(IN) :: n INTEGER :: i, factorsum isPerfect = .FALSE. factorsum = 1 DO i = 2, INT(SQRT(REAL(n))) IF(MOD(n, i) == 0) factorsum = factorsum + i + (n / i) END DO IF (factorsum == n) isPerfect = .TRUE. END FUNCTION isPerfect
Haskell
perf n = n == sum [i | i <- [1..n-1], n `mod` i == 0]
J
is_perfect=: = [: +/ ((0=]|[)i.) # i.
The program defined above, like programs found here in other languages, assumes that the input will be a scalar positive integer.
Examples of use, including extensions beyond those assumptions:
is_perfect 33550336 1 }.I. is_perfect"0 i. 10000 6 28 496 8128 ] zero_through_twentynine =. i. 3 10 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 is_pos_int=: 0&< *. ]=>. (is_perfect"0 *. is_pos_int) zero_through_twentynine 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
Java
<java>public static boolean perf(int n){ int sum= 0; for(int i= 1;i < n;i++){ if(n % i == 0){ sum+= i; } } return sum == n; }</java> Or for arbitrary precision: <java>import java.math.BigInteger;
public static boolean perf(BigInteger n){ BigInteger sum= BigInteger.ZERO; for(BigInteger i= BigInteger.ONE; i.compareTo(n) < 0;i=i.add(BigInteger.ONE)){ if(n.mod(i).compareTo(BigInteger.ZERO) == 0){ sum= sum.add(i); } } return sum.compareTo(n) == 0; }</java>
MAXScript
fn isPerfect n = ( local sum = 0 for i in 1 to (n-1) do ( if mod n i == 0 then ( sum += i ) ) sum == n )
Perl
<perl>sub perf {
my $n = shift; my $sum = 0; foreach my $i (1..$n-1) { if ($n % $i == 0) { $sum += $i; } } return $sum == $n;
}</perl> Functional style: <perl>use List::Util qw(sum);
sub perf {
my $n = shift; $n == sum(grep {$n % $_ == 0} 1..$n-1);
}</perl>
Python
<python>def perf(n):
sum = 0 for i in xrange(1, n): if n % i == 0: sum += i return sum == n</python>
Functional style: <python>perf = lambda n: n == sum(i for i in xrange(1, n) if n % i == 0)</python>
Ruby
def perf(n)
sum = 0 for i in 1..n-1 if n % i == 0 sum += i end end return sum == n
end Functional style: def perf(n)
n == (1..n-1).select {|i| n % i == 0}.inject(0) {|sum, i| sum + i}
end
Scheme
<scheme>(define (perf n)
(let loop ((i 1) (sum 0)) (cond ((= i n) (= sum n)) ((= 0 (modulo n i)) (loop (+ i 1) (+ sum i))) (else (loop (+ i 1) sum)))))</scheme>