Radical of an integer: Difference between revisions
m
→{{header|ALGOL 68}}: Fixed note about specifying the heap size
(Added Sidef) |
m (→{{header|ALGOL 68}}: Fixed note about specifying the heap size) |
||
| (4 intermediate revisions by the same user 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 1,015 ⟶ 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,220 ⟶ 2,360:
Total: 78,735
</pre>
=={{header|
<syntaxhighlight lang="rexx">
/* REXX */
Line 2,366 ⟶ 2,506:
9 83.6 seconds
10 100.6 seconds</pre>
=={{header|RPL}}==
| |||