Perfect Numbers

From Rosetta Code

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 (2ⁿ - 1) × 2^{n - 1}. It is not known if there are any odd perfect numbers.

Contents 1 Ada 2 ALGOL 68 3 BASIC 4 C 5 D 6 Forth 7 Haskell 8 J 9 Java 10 Python

[edit] 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;
 

[edit] 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

[edit] BASIC

Works with: QuickBasic version 4.5

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

[edit] C

Based on the D version, for GCC:

 
#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;
}
 

[edit] D

Based on the Algol version:

 
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);
}
 

[edit] Forth

: perfect? ( n -- ? )
  1
  over 2/ 1+ 2 ?do
    over i mod 0= if i + then
  loop
  = ;

[edit] Haskell

perf n = n == sum [i | i <- [1..n-1], n `mod` i == 0]

[edit] 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

[edit] 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;
}

Or for arbitrary precision:

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

[edit] Python

def perf(n):
    sum = 0
    for i in xrange(1, n):
        if n % i == 0:
            sum += i
    return sum == n

Functional style:

perf = lambda n: n == sum(i for i in xrange(1, n) if n % i == 0)