Perfect numbers
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
<lang 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; </lang>
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
<lang 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</lang>
C
Based on the D version, for GCC: <lang 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;
} </lang>
C++
for gcc/g++ <lang C++>
- include <iostream>
using namespace std ;
bool is_perfect( int ) ;
int main( ) {
cout << "Perfect numbers from 1 to 33550337:\n" ;
for ( int num = 1 ; num < 33550337 ; num++ ) {
if ( is_perfect( num ) )
cout << num << '\n' ;
}
return 0 ;
}
bool is_perfect( int number ) {
int sum = 0 ;
for ( int i = 1 ; i < number + 1 ; i++ )
if ( number % i == 0 )
sum += i ;
return ( ( sum == 2 * number ) || ( sum - number == number ) ) ;
} </lang>
D
Based on the Algol version: <lang 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);
} </lang>
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
<lang 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; }</lang> Or for arbitrary precision: <lang 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; }</lang>
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
)
OCaml
<lang ocaml>let perf n =
let sum = ref 0 in
for i = 1 to n-1 do
if n mod i = 0 then
sum := !sum + i
done;
!sum = n</lang>
Functional style: <lang ocaml>(* range operator *) let rec (--) a b =
if a > b then [] else a :: (a+1) -- b
let perf n = n = List.fold_left (+) 0 (List.filter (fun i -> n mod i = 0) (1 -- (n-1)))</lang>
Perl
<lang perl>sub perf {
my $n = shift;
my $sum = 0;
foreach my $i (1..$n-1) {
if ($n % $i == 0) {
$sum += $i;
}
}
return $sum == $n;
}</lang> Functional style: <lang perl>use List::Util qw(sum);
sub perf {
my $n = shift;
$n == sum(grep {$n % $_ == 0} 1..$n-1);
}</lang>
Python
<lang python>def perf(n):
sum = 0
for i in xrange(1, n):
if n % i == 0:
sum += i
return sum == n</lang>
Functional style: <lang python>perf = lambda n: n == sum(i for i in xrange(1, n) if n % i == 0)</lang>
Ruby
<lang ruby>def perf(n)
sum = 0
for i in 1...n
if n % i == 0
sum += i
end
end
return sum == n
end</lang> Functional style: <lang ruby>def perf(n)
n == (1...n).select {|i| n % i == 0}.inject(0) {|sum, i| sum + i}
end</lang>
Scheme
<lang 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)))))</lang>