Rosetta Code

Multiplicatively perfect numbers: Difference between revisions

Page Discussion

Multiplicatively perfect numbers (view source)

Revision as of 21:38, 9 May 2024

11,254 bytes added ,  19 days ago
Added Easylang
(Added BASIC256, True BASIC, PureBasic and Yabasic.)
(Added Easylang)
 
(7 intermediate revisions by 6 users not shown)
Line 303:
Counts under 500,000: MPNs = 108,223 Semi-primes = 108,326
Counts under 5,000,000: MPNs = 978,983 Semi-primes = 979,274
</pre>
 
=={{header|C++}}==
<syntaxhighlight lang=C++>#include <iostream>
#include <vector>
#include <numeric>
 
std::vector<int> divisors( int n ) {
std::vector<int> divisors ;
for ( int i = 1 ; i < n + 1 ; i++ ) {
if ( n % i == 0 )
divisors.push_back( i ) ;
}
return divisors ;
}
 
int main( ) {
std::vector<int> multi_perfect ;
for ( int i = 1 ; i < 501 ; i++ ) {
std::vector<int> divis { divisors( i ) } ;
if ( std::accumulate( divis.begin( ) , divis.end( ) , 1 ,
std::multiplies<int>() ) == (i * i ) )
multi_perfect.push_back( i ) ;
}
std::cout << '(' ;
int count = 1 ;
for ( int i : multi_perfect ) {
std::cout << i << ' ' ;
if ( count % 15 == 0 )
std::cout << '\n' ;
count++ ;
}
std::cout << ")\n" ;
return 0 ;
}</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
)
</pre>
 
=={{header|EasyLang}}==
<syntaxhighlight>
for n = 1 to 500
pro = 1
for m = 2 to n div 2
if n mod m = 0
pro *= m
.
.
if n = pro
write n & " "
.
.
</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
</pre>
 
Line 546 ⟶ 613:
 
Counts under 500000: MPNs = 108222 Semi-primes = 108326
</pre>
 
=={{header|Nim}}==
In our solution, 1 is not considered to be a multiplicatively perfect number.
 
Using 32 bits integers rather than 64 bits integers improves considerably the performance. With a limit set to 5_000_000 and 64 bits integers, the program runs in around 10 seconds. This time drops to 3 seconds if 32 bits integers are used.
<syntaxhighlight lang="Nim">import std/strformat
 
func isMPN(n: int32): bool =
## Return true if "n" is a multiplicatively perfect number.
## We consider than 1 is not an MPN.
var first, second = 0i32 # First and second proper divisors.
let delta = 1 + (n and 1)
var d = delta + 1
while d * d <= n:
if n mod d == 0:
if second != 0: return false # More than two proper divisors.
first = d
let q = n div d
if q != d: second = q
inc d, delta
result = first * second == n
 
### Task ###
var count = 0
for n in 1i32..499i32:
if n.isMPN:
inc count
stdout.write &"{n:3}"
stdout.write if count mod 10 == 0: '\n' else: ' '
echo '\n'
 
### Stretch task ###
 
func isPrime(n: int32): bool =
## Return true if "n" is prime.
if n < 2: return false
if (n and 1) == 0: return n == 2
if n mod 3 == 0: return n == 3
var k = 5
var delta = 2
while k * k <= n:
if n mod k == 0: return false
inc k, delta
delta = 6 - delta
result = true
 
var mpnCount = 0
var limit = 500i32
var ns, nc = 3i32
var squares, cubes = 1i32
var n = 1i32
while true:
inc n
if n == limit:
while ns * ns < limit:
if ns.isPrime: inc squares
inc ns, 2
while nc * nc * nc < limit:
if nc.isPrime: inc cubes
inc nc, 2
echo &"Under {limit} there are {mpnCount} MPNs and {mpnCount - cubes + squares} semi-primes."
if limit == 500_000: break
limit *= 10
if n.isMPN: inc mpnCount
</syntaxhighlight>
 
{{out]]
<pre> 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
 
Under 500 there are 149 MPNs and 153 semi-primes.
Under 5000 there are 1353 MPNs and 1365 semi-primes.
Under 50000 there are 12073 MPNs and 12110 semi-primes.
Under 500000 there are 108222 MPNs and 108326 semi-primes.
</pre>
 
=={{header|Perl}}==
{{trans|Raku}}
{{libheader|ntheory}}
<syntaxhighlight lang="perl" line>
use v5.36;
use enum <false true>;
use ntheory <is_prime nth_prime is_semiprime gcd>;
 
sub comma { reverse ((reverse shift) =~ s/.{3}\K/,/gr) =~ s/^,//r }
sub table (@V) { my $t = 10 * (my $w = 5); ( sprintf( ('%'.$w.'d')x@V, @V) ) =~ s/.{1,$t}\K/\n/gr }
 
sub find_factor ($n, $constant = 1) { # NB: required that n > 1
my($x, $rho, $factor) = (2, 1, 1);
while ($factor == 1) {
$rho *= 2;
my $fixed = $x;
for (0..$rho) {
$x = ( $x * $x + $constant ) % $n;
$factor = gcd(($x-$fixed), $n);
last if 1 < $factor;
}
}
$factor = find_factor($n, $constant+1) if $n == $factor;
$factor
}
 
# Call with range 1..$limit
sub is_mpn($n) {
state $cube = 1; $cube = 1 if $n == 1; # set and reset
$n == 1 ? return true : is_prime($n) ? return false : ();
++$cube, return true if $n == nth_prime($cube)**3;
my $factor = find_factor($n);
my $div = int $n/$factor;
return true if is_prime $factor and is_prime $div and $div != $factor;
false
}
 
say "Multiplicatively perfect numbers less than 500:\n" . table grep is_mpn($_), 1..499;
 
say 'There are:';
for my $limit (5e2, 5e3, 5e4, 5e5, 5e6) {
my($m,$s) = (0,0);
is_mpn $_ and $m++ for 1..$limit-1;
is_semiprime $_ and $s++ for 1..$limit-1;
printf "%8s MPNs less than %8s, %8s semiprimes\n", comma($m), $limit, comma $s
}
</syntaxhighlight>
{{out}}
<pre>
Multiplicatively perfect numbers less than 500:
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
 
There are:
150 MPNs less than 500, 153 semiprimes
1,354 MPNs less than 5000, 1,365 semiprimes
12,074 MPNs less than 50000, 12,110 semiprimes
108,223 MPNs less than 500000, 108,326 semiprimes
978,983 MPNs less than 5000000, 979,274 semi primes
</pre>
 
Line 917 ⟶ 1,146:
497 = 7 x 71
done...
</pre>
 
=={{header|RPL}}==
{{works with|HP|49}}
≪ { 1 }
2 ROT '''FOR''' j
'''IF''' j SQ j DIVIS ΠLIST == '''THEN''' j + '''END'''
'''NEXT'''
≫ '<span style="color:blue">TASK</span>' STO
≪ (1,0)
2 ROT '''FOR''' j
j DIVIS
'''IF CASE'''
DUP SIZE DUP 4 > OVER " < '''THEN''' NOT '''END'''
3 == '''THEN''' 1 '''END'''
DUP 2 GET OVER 3 GET GCD 1 == '''END'''
'''THEN''' SWAP (0,1) + SWAP '''END'''
'''IF''' ΠLIST j SQ == '''THEN''' 1 + '''END'''
'''NEXT'''
≫ '<span style="color:blue">STRETCH</span>' STO
 
500 <span style="color:blue">TASK</span>
500 <span style="color:blue">STRETCH</span>
{{out}}
<pre>
2: { 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 }
1: (150,153)
</pre>
 
=={{header|Rust}}==
<syntaxhighlight lang="rust">fn divisors( num : u128 ) -> Vec<u128> {
(1..= num).filter( | &d | num % d == 0 ).collect( )
}
 
fn main() {
println!("{:?}" , (1..= 500).filter( | &d | {
let divis : Vec<u128> = divisors( d ) ;
let prod : u128 = divis.iter( ).product( ) ;
prod == d.checked_pow( 2 ).unwrap( )
}).collect::<Vec<u128>>( ) ) ;
}</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]
</pre>
 
 
=={{header|Sidef}}==
<syntaxhighlight lang="ruby">func multiplicatively_perfect_numbers(N) {
[1] + semiprimes(N).grep{|n| isqrt(n**tau(n)) == n.sqr } + N.icbrt.primes.map { .cube } -> sort
}
 
say ("Terms <= 500: ", multiplicatively_perfect_numbers(500).join(' '), "\n")
 
for n in (500, 5_000, 50_000, 500_000) {
var M = multiplicatively_perfect_numbers(n)
say "There are #{M.len} MPNs and #{semiprime_count(n)} semiprimes <= #{n.commify}."
}</syntaxhighlight>
{{out}}
<pre>
Terms <= 500: 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
 
There are 150 MPNs and 153 semiprimes <= 500.
There are 1354 MPNs and 1365 semiprimes <= 5,000.
There are 12074 MPNs and 12110 semiprimes <= 50,000.
There are 108223 MPNs and 108326 semiprimes <= 500,000.
</pre>
 
Line 923 ⟶ 1,219:
{{libheader|Wren-fmt}}
This includes '1' as an MPN. Not very quick at around 112 seconds but reasonable for Wren.
<syntaxhighlight lang="ecmascriptwren">import "./math" for Int, Nums
import "./fmt" for Fmt
 
Chkas
2,022

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/342733...364357"