Multiplicatively perfect numbers: Difference between revisions

=={{header|ALGOL 68}}==

{{libheader|ALGOL 68-primes}}

Uses sieves, counts 1 as a multiplicatively perfect number.<br>

As with the Phix and probably other samples, uses the fact that the multiplicatively perfect numbers (other than 1) must have three proper divisors - see OIES A007422.

<syntaxhighlight lang="algol68">

BEGIN # find multiplicatively perfect numbers - numbers whose proper #

# divisor product is the number itself ( includes 1 ) #

PR read "primes.incl.a68" PR # include prime utilties #

INT max number = 500 000; # largest number we wlil consider #

[]BOOL prime = PRIMESIEVE max number; # sieve the primes to max number #

[ 1 : max number ]INT pdc; # table of proper divisor counts #

[ 1 : max number ]INT pfc; # table of prime factor counts #

# count the proper divisors and prime factors #

FOR n TO UPB pdc DO pdc[ n ] := 1; pfc[ n ] := 0 OD;

FOR i FROM 2 TO UPB pdc DO

BOOL is prime = prime[ i ];

INT m := 1; # j will be the mth multiple of i #

FOR j FROM i + i BY i TO UPB pdc DO

pdc[ j ] +:= 1;

IF prime[ m +:= 1 ] THEN # j is a prime multiple of m #

pfc[ j ] +:= 1;

IF i = m THEN # j is i squared #

pfc[ j ] +:= 1

FI

ELSE # j is not a prime multiple of i #

pfc[ j ] +:= pfc[ m ] # add the prime factor count of m #

FI

OD

OD;

# find the mutiplicatively perfect numbers #

INT mp count := 0;

INT sp count := 0;

INT next to show := 500;

FOR n TO UPB pdc DO

IF n = 1 OR pdc[ n ] = 3 THEN

# n is 1 or has 3 proper divisors so is muktiplicatively perfect #

# number - see OEIS A007422 #

mp count +:= 1;

IF n < 500 THEN

print( ( " ", whole( n, -3 ) ) );

IF mp count MOD 10 = 0 THEN print( ( newline ) ) FI

FI

FI;

IF pfc[ n ] = 2 THEN

# 2 prime factors, n is semi-prime #

sp count +:= 1

FI;

IF n = next to show THEN

print( ( "Up to ", whole( next to show, -8 )

, " there are ", whole( mp count, -6 )

, " multiplicatively perfect numbers and ", whole( sp count, -6 )

, " semi-primes", newline

)

);

next to show *:= 10

FI

OD

END

</syntaxhighlight>

{{out}}

<pre>

1 6 8 10 14 15 21 22 26 27

33 34 35 38 39 46 51 55 57 58

62 65 69 74 77 82 85 86 87 91

93 94 95 106 111 115 118 119 122 123

125 129 133 134 141 142 143 145 146 155

158 159 161 166 177 178 183 185 187 194

201 202 203 205 206 209 213 214 215 217

218 219 221 226 235 237 247 249 253 254

259 262 265 267 274 278 287 291 295 298

299 301 302 303 305 309 314 319 321 323

326 327 329 334 335 339 341 343 346 355

358 362 365 371 377 381 382 386 391 393

394 395 398 403 407 411 413 415 417 422

427 437 445 446 447 451 453 454 458 466

469 471 473 478 481 482 485 489 493 497

Up to 500 there are 150 multiplicatively perfect numbers and 153 semi-primes

Up to 5000 there are 1354 multiplicatively perfect numbers and 1365 semi-primes

Up to 50000 there are 12074 multiplicatively perfect numbers and 12110 semi-primes

Up to 500000 there are 108223 multiplicatively perfect numbers and 108326 semi-primes

</pre>