Radical of an integer: Difference between revisions
m
→{{header|ALGOL 68}}: Fixed note about specifying the heap size
(Added Python Implementation for Radical of an Integer Task) |
m (→{{header|ALGOL 68}}: Fixed note about specifying the heap size) |
||
| (6 intermediate revisions by 3 users not shown) | |||
Line 28:
* OEIS sequence [[oeis:A007947|A007947: Largest square free number dividing n]]
<br>
=={{header|ALGOL 68}}==
When running this with ALGOL 68G, a large heap size will need to be specified, e.g.: with <code>-heap 256M</code> on the command line.<br/>
Builds tables of radicals and unique prime factor counts to avoid factorising the numbers.
<syntaxhighlight lang="algol68">
BEGIN # find the radicals of some integers - the radical of n is the product #
# of thr the distinct prime factors of n, the radical of 1 is 1 #
INT max number = 1 000 000; # maximum number we will consider #
[ 1 : max number ]INT upfc; # unique prime factor counts #
[ 1 : max number ]INT radical; # table of radicals #
FOR i TO UPB upfc DO upfc[ i ] := 0; radical[ i ] := 1 OD;
FOR i FROM 2 TO UPB upfc DO
IF upfc[ i ] = 0 THEN
radical[ i ] := i;
upfc[ i ] := 1;
FOR j FROM i + i BY i TO UPB upfc DO
upfc[ j ] +:= 1;
radical[ j ] *:= i
OD
FI
OD;
# show the radicals of the first 50 positive integers #
print( ( "Radicals of 1 to 50:", newline ) );
FOR i TO 50 DO
print( ( whole( radical[ i ], -5 ) ) );
IF i MOD 10 = 0 THEN print( ( newline ) ) FI
OD;
# radicals of some specific numbers #
print( ( newline ) );
print( ( "Radical of 99999: ", whole( radical[ 99999 ], 0 ), newline ) );
print( ( "Radical of 499999: ", whole( radical[ 499999 ], 0 ), newline ) );
print( ( "Radical of 999999: ", whole( radical[ 999999 ], 0 ), newline ) );
print( ( newline ) );
# find the maximum number of unique prime factors #
INT max upfc := 0;
# show the distribution of the unique prime factor counts #
FOR i TO UPB upfc DO IF upfc[ i ] > max upfc THEN max upfc := upfc[ i ] FI OD;
[ 0 : max upfc ]INT dpfc; FOR i FROM LWB dpfc TO UPB dpfc DO dpfc[ i ] := 0 OD;
FOR i TO UPB upfc DO
dpfc[ upfc[ i ] ] +:= 1
OD;
print( ( "Distribution of radicals:", newline ) );
FOR i FROM LWB dpfc TO UPB dpfc DO
print( ( whole( i, -2 ), ": ", whole( dpfc[ i ], 0 ), newline ) )
OD
END
</syntaxhighlight>
{{out}}
<pre>
Radicals of 1 to 50:
1 2 3 2 5 6 7 2 3 10
11 6 13 14 15 2 17 6 19 10
21 22 23 6 5 26 3 14 29 30
31 2 33 34 35 6 37 38 39 10
41 42 43 22 15 46 47 6 7 10
Radical of 99999: 33333
Radical of 499999: 3937
Radical of 999999: 111111
Distribution of radicals:
0: 1
1: 78734
2: 288726
3: 379720
4: 208034
5: 42492
6: 2285
7: 8
</pre>
=={{header|C}}==
Line 461 ⟶ 532:
6: 2285
7: 8</pre>
=={{header|EasyLang}}==
<syntaxhighlight>
fastfunc radnf num .
d = 2
while d <= sqrt num
if num mod d = 0
nf += 1
while num mod d = 0
num /= d
.
.
d += 1
.
if d <= num
nf += 1
.
return nf
.
func rad num .
r = 1
d = 2
while d <= sqrt num
if num mod d = 0
r *= d
while num mod d = 0
num /= d
.
.
d += 1
.
if d <= num
r *= num
.
return r
.
proc show50 . .
write "First 50 radicals:"
for n = 1 to 50
write " " & rad n
.
print ""
.
proc show n . .
print "radical(" & n & ") = " & rad n
.
proc dist . .
len dist[] 7
for n = 2 to 1000000
dist[radnf n] += 1
.
print ""
print "Distribution of radicals:"
print "0: 1"
for i = 1 to 7
print i & ": " & dist[i]
.
.
show50
print ""
show 99999
show 499999
show 999999
print ""
dist
</syntaxhighlight>
=={{header|FreeBASIC}}==
Line 949 ⟶ 1,086:
-----------------------------------------
Overall total: 78735
</pre>
=={{header|Lua}}==
{{Trans|ALGOL 68}}
<syntaxhighlight lang="lua">
do -- find the radicals of some integers - the radical of n is the product
-- of the distinct prime factors of n, the radical of 1 is 1
local maxNumber = 1000000; -- maximum number we will consider
local upfc, radical = {}, {} -- unique prime factor counts and radicals
for i = 1, maxNumber do
upfc[ i ] = 0
radical[ i ] = 1
end
for i = 2, maxNumber do
if upfc[ i ] == 0 then
radical[ i ] = i
upfc[ i ] = 1
for j = i + i, maxNumber, i do
upfc[ j ] = upfc[ j ] + 1
radical[ j ] = radical[ j ] * i
end
end
end
-- show the radicals of the first 50 positive integers
io.write( "Radicals of 1 to 50:\n" )
for i = 1, 50 do
io.write( string.format( "%5d", radical[ i ] ), ( i % 10 == 0 and "\n" or "" ) )
end
-- radicals of some specific numbers
io.write( "\n" )
io.write( "Radical of 99999: ", radical[ 99999 ], "\n" )
io.write( "Radical of 499999: ", radical[ 499999 ], "\n" )
io.write( "Radical of 999999: ", radical[ 999999 ], "\n" )
io.write( "\n" )
-- show the distribution of the unique prime factor counts
local dpfc = {}
for i = 1, maxNumber do
local count = dpfc[ upfc[ i ] ]
dpfc[ upfc[ i ] ] = ( count == nil and 1 or count + 1 )
end
io.write( "Distribution of radicals:\n" )
for i = 0, #dpfc do
io.write( string.format( "%2d", i ), ": ", dpfc[ i ], "\n" )
end
end
</syntaxhighlight>
{{out}}
<pre>
Radicals of 1 to 50:
1 2 3 2 5 6 7 2 3 10
11 6 13 14 15 2 17 6 19 10
21 22 23 6 5 26 3 14 29 30
31 2 33 34 35 6 37 38 39 10
41 42 43 22 15 46 47 6 7 10
Radical of 99999: 33333
Radical of 499999: 3937
Radical of 999999: 111111
Distribution of radicals:
0: 1
1: 78734
2: 288726
3: 379720
4: 208034
5: 42492
6: 2285
7: 8
</pre>
Line 2,154 ⟶ 2,360:
Total: 78,735
</pre>
=={{header|
<syntaxhighlight lang="rexx">
/* REXX */
Line 2,300 ⟶ 2,506:
9 83.6 seconds
10 100.6 seconds</pre>
=={{header|RPL}}==
Line 2,377 ⟶ 2,581:
Number of primes and powers of primes less than or equal to 1000000: 78734
</pre>
=={{header|Sidef}}==
Takes less than one second to run:
<syntaxhighlight lang="ruby">with (50) {|n|
say "Radicals of the first #{n} positive integers:"
1..n -> map { .rad }.each_slice(10, {|*s|
say s.map { '%2s' % _ }.join(' ')
})
}
say ''; [99999, 499999, 999999].map {|n|
say "rad(#{n}) = #{rad(n)}"
}
for limit in (1e6, 1e7, 1e8, 1e9) {
say "\nCounting of k-omega primes <= #{limit.commify}:"
for k in (1..Inf) {
break if (pn_primorial(k) > limit)
var c = k.omega_prime_count(limit)
say "#{k}: #{c}"
assert_eq(c, limit.prime_power_count) if (k == 1)
}
}</syntaxhighlight>
{{out}}
<pre>
Radicals of the first 50 positive integers:
1 2 3 2 5 6 7 2 3 10
11 6 13 14 15 2 17 6 19 10
21 22 23 6 5 26 3 14 29 30
31 2 33 34 35 6 37 38 39 10
41 42 43 22 15 46 47 6 7 10
rad(99999) = 33333
rad(499999) = 3937
rad(999999) = 111111
Counting of k-omega primes <= 1,000,000:
1: 78734
2: 288726
3: 379720
4: 208034
5: 42492
6: 2285
7: 8
Counting of k-omega primes <= 10,000,000:
1: 665134
2: 2536838
3: 3642766
4: 2389433
5: 691209
6: 72902
7: 1716
8: 1
Counting of k-omega primes <= 100,000,000:
1: 5762859
2: 22724609
3: 34800362
4: 25789580
5: 9351293
6: 1490458
7: 80119
8: 719
Counting of k-omega primes <= 1,000,000,000:
1: 50851223
2: 206415108
3: 332590117
4: 269536378
5: 114407511
6: 24020091
7: 2124141
8: 55292
9: 138
</pre>
Line 2,383 ⟶ 2,663:
{{libheader|Wren-seq}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="
import "./seq" for Lst
import "./fmt" for Fmt
| |||