Perfect numbers: Difference between revisions
No edit summary |
|||
Line 46: | Line 46: | ||
=={{header|BASIC}}== |
=={{header|BASIC}}== |
||
{{works with|QuickBasic|4.5}} |
{{works with|QuickBasic|4.5}} |
||
<qbasic>FUNCTION perf(n) |
<lang qbasic>FUNCTION perf(n) |
||
sum = 0 |
sum = 0 |
||
for i = 1 to n - 1 |
for i = 1 to n - 1 |
||
Line 58: | Line 58: | ||
perf = 0 |
perf = 0 |
||
END IF |
END IF |
||
END FUNCTION</ |
END FUNCTION</lang> |
||
=={{header|C}}== |
=={{header|C}}== |
||
Based on the D version, for GCC: |
Based on the D version, for GCC: |
||
<c> |
<lang c> |
||
#include "stdio.h" |
#include "stdio.h" |
||
#include "math.h" |
#include "math.h" |
||
Line 90: | Line 90: | ||
return 0; |
return 0; |
||
} |
} |
||
</ |
</lang> |
||
=={{header|D}}== |
=={{header|D}}== |
||
Based on the Algol version: |
Based on the Algol version: |
||
<d> |
<lang d> |
||
import std.math: sqrt; |
import std.math: sqrt; |
||
Line 119: | Line 119: | ||
printf("%d\n", n); |
printf("%d\n", n); |
||
} |
} |
||
</ |
</lang> |
||
=={{header|Forth}}== |
=={{header|Forth}}== |
||
Line 168: | Line 168: | ||
=={{header|Java}}== |
=={{header|Java}}== |
||
<java>public static boolean perf(int n){ |
<lang java>public static boolean perf(int n){ |
||
int sum= 0; |
int sum= 0; |
||
for(int i= 1;i < n;i++){ |
for(int i= 1;i < n;i++){ |
||
Line 176: | Line 176: | ||
} |
} |
||
return sum == n; |
return sum == n; |
||
}</ |
}</lang> |
||
Or for arbitrary precision:[[Category:Arbitrary precision]] |
Or for arbitrary precision:[[Category:Arbitrary precision]] |
||
<java>import java.math.BigInteger; |
<lang java>import java.math.BigInteger; |
||
public static boolean perf(BigInteger n){ |
public static boolean perf(BigInteger n){ |
||
Line 189: | Line 189: | ||
} |
} |
||
return sum.compareTo(n) == 0; |
return sum.compareTo(n) == 0; |
||
}</ |
}</lang> |
||
=={{header|MAXScript}}== |
=={{header|MAXScript}}== |
||
Line 206: | Line 206: | ||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
<perl>sub perf { |
<lang perl>sub perf { |
||
my $n = shift; |
my $n = shift; |
||
my $sum = 0; |
my $sum = 0; |
||
Line 215: | Line 215: | ||
} |
} |
||
return $sum == $n; |
return $sum == $n; |
||
}</ |
}</lang> |
||
Functional style: |
Functional style: |
||
<perl>use List::Util qw(sum); |
<lang perl>use List::Util qw(sum); |
||
sub perf { |
sub perf { |
||
my $n = shift; |
my $n = shift; |
||
$n == sum(grep {$n % $_ == 0} 1..$n-1); |
$n == sum(grep {$n % $_ == 0} 1..$n-1); |
||
}</ |
}</lang> |
||
=={{header|Python}}== |
=={{header|Python}}== |
||
<python>def perf(n): |
<lang python>def perf(n): |
||
sum = 0 |
sum = 0 |
||
for i in xrange(1, n): |
for i in xrange(1, n): |
||
if n % i == 0: |
if n % i == 0: |
||
sum += i |
sum += i |
||
return sum == n</ |
return sum == n</lang> |
||
Functional style: |
Functional style: |
||
<python>perf = lambda n: n == sum(i for i in xrange(1, n) if n % i == 0)</ |
<lang python>perf = lambda n: n == sum(i for i in xrange(1, n) if n % i == 0)</lang> |
||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
<ruby>def perf(n) |
<lang ruby>def perf(n) |
||
sum = 0 |
sum = 0 |
||
for i in 1...n |
for i in 1...n |
||
Line 243: | Line 243: | ||
end |
end |
||
return sum == n |
return sum == n |
||
end</ |
end</lang> |
||
Functional style: |
Functional style: |
||
<ruby>def perf(n) |
<lang ruby>def perf(n) |
||
n == (1...n).select {|i| n % i == 0}.inject(0) {|sum, i| sum + i} |
n == (1...n).select {|i| n % i == 0}.inject(0) {|sum, i| sum + i} |
||
end</ |
end</lang> |
||
=={{header|Scheme}}== |
=={{header|Scheme}}== |
||
<scheme>(define (perf n) |
<lang scheme>(define (perf n) |
||
(let loop ((i 1) |
(let loop ((i 1) |
||
(sum 0)) |
(sum 0)) |
||
Line 258: | Line 258: | ||
(loop (+ i 1) (+ sum i))) |
(loop (+ i 1) (+ sum i))) |
||
(else |
(else |
||
(loop (+ i 1) sum)))))</ |
(loop (+ i 1) sum)))))</lang> |
Revision as of 15:44, 3 February 2009
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
<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>
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 )
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>