Rosetta Code

Radical of an integer: Difference between revisions

← Older edit
Content deleted Content added
Not a robot (talk | contribs)
2,162 edits
Add Cowgol
Chkas (talk | contribs)
2,822 edits
 
(21 intermediate revisions by 11 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 117 ⟶ 188:
6: 2285
7: 8</pre>
 
=={{header|C++}}==
<syntaxhighlight lang="cpp">#include <iomanip>
#include <iostream>
#include <map>
#include <vector>
 
int radical(int n, int& count) {
if (n == 1) {
count = 1;
return 1;
}
int product = 1;
count = 0;
if ((n & 1) == 0) {
product *= 2;
++count;
while ((n & 1) == 0)
n >>= 1;
}
for (int p = 3, sq = 9; sq <= n; p += 2) {
if (n % p == 0) {
product *= p;
++count;
while (n % p == 0)
n /= p;
}
sq += (p + 1) << 2;
}
if (n > 1) {
product *= n;
++count;
}
return product;
}
 
std::vector<bool> prime_sieve(int limit) {
std::vector<bool> sieve(limit, true);
if (limit > 0)
sieve[0] = false;
if (limit > 1)
sieve[1] = false;
for (int i = 4; i < limit; i += 2)
sieve[i] = false;
for (int p = 3, sq = 9; sq < limit; p += 2) {
if (sieve[p]) {
for (int q = sq; q < limit; q += p << 1)
sieve[q] = false;
}
sq += (p + 1) << 2;
}
return sieve;
}
 
int main() {
std::cout.imbue(std::locale(""));
std::cout << "Radicals of the first 50 positive integers:\n";
int count = 0;
for (int i = 1; i <= 50; ++i) {
std::cout << std::setw(2) << radical(i, count)
<< (i % 10 == 0 ? '\n' : ' ');
}
std::cout << '\n';
for (int i : {99999, 499999, 999999}) {
std::cout << "Radical of " << std::setw(7) << i << " is "
<< std::setw(7) << radical(i, count) << ".\n";
}
std::map<int, int> prime_factors;
const int limit = 1000000;
for (int i = 1; i <= limit; ++i) {
radical(i, count);
++prime_factors[count];
}
std::cout << "\nRadical factor count breakdown up to " << limit << ":\n";
for (const auto& [count, total] : prime_factors) {
std::cout << count << ": " << std::setw(7) << total << '\n';
}
auto sieve = prime_sieve(limit + 1);
int primes = 0, prime_powers = 0;
for (int i = 1; i <= limit; ++i) {
if (sieve[i]) {
++primes;
int n = limit;
while (i <= n / i) {
++prime_powers;
n /= i;
}
}
}
std::cout << "\nUp to " << limit << ":\n";
std::cout << "Primes: " << std::setw(6) << primes
<< "\nPowers: " << std::setw(6) << prime_powers
<< "\nPlus 1: " << std::setw(6) << 1
<< "\nTotal: " << std::setw(6) << primes + prime_powers + 1
<< '\n';
}</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
 
Radical of 99,999 is 33,333.
Radical of 499,999 is 3,937.
Radical of 999,999 is 111,111.
 
Radical factor count breakdown up to 1,000,000:
1: 78,735
2: 288,726
3: 379,720
4: 208,034
5: 42,492
6: 2,285
7: 8
 
Up to 1,000,000:
Primes: 78,498
Powers: 236
Plus 1: 1
Total: 78,735
</pre>
 
=={{header|CLU}}==
<syntaxhighlight lang="clu">distinct_factors = iter (n: int) yields (int)
if n // 2 = 0 then
yield(2)
while n // 2 = 0 do n := n / 2 end
end
 
div: int := 3
while div <= n do
if n // div = 0 then
yield(div)
while n // div = 0 do n := n / div end
end
div := div + 2
end
end distinct_factors
 
radical = proc (n: int) returns (int)
rad: int := 1
for fac: int in distinct_factors(n) do
rad := rad * fac
end
return(rad)
end radical
 
dpf_count = proc (n: int) returns (int)
count: int := 0
for fac: int in distinct_factors(n) do
count := count + 1
end
return(count)
end dpf_count
 
show_first_50 = proc (out: stream)
stream$putl(out, "Radicals of 1..50:")
for n: int in int$from_to(1, 50) do
stream$putright(out, int$unparse(radical(n)), 5)
if n // 10 = 0 then stream$putl(out, "") end
end
end show_first_50
 
show_radical = proc (out: stream, n: int)
stream$puts(out, "The radical of ")
stream$puts(out, int$unparse(n))
stream$puts(out, " is ")
stream$puts(out, int$unparse(radical(n)))
stream$putl(out, ".")
end show_radical
 
find_distribution = proc (out: stream)
dist: array[int] := array[int]$fill(0, 8, 0)
for n: int in int$from_to(1, 1000000) do
stream$putright(out, int$unparse(n) || "\r", 8)
dpf: int := dpf_count(n)
dist[dpf] := dist[dpf] + 1
end
 
stream$putl(out, "Distribution of radicals:")
for dpf: int in array[int]$indexes(dist) do
stream$putright(out, int$unparse(dpf), 1)
stream$puts(out, ": ")
stream$putright(out, int$unparse(dist[dpf]), 8)
stream$putl(out, "")
end
end find_distribution
 
start_up = proc ()
po: stream := stream$primary_output()
 
show_first_50(po)
stream$putl(po, "")
 
for n: int in array[int]$elements(array[int]$[99999, 499999, 999999]) do
show_radical(po, n)
end
stream$putl(po, "")
 
find_distribution(po)
end start_up</syntaxhighlight>
{{out}}
<pre>Radicals of 1..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
 
The radical of 99999 is 33333.
The radical of 499999 is 3937.
The radical of 999999 is 111111.
 
Distribution of radicals:
0: 1
1: 78734
2: 288726
3: 379720
4: 208034
5: 42492
6: 2285
7: 8</pre>
 
=={{header|Cowgol}}==
<syntaxhighlight lang="cowgol">include "cowgol.coh";
Line 234 ⟶ 532:
6: 2285
7: 8</pre>
 
=={{header|EasyLang}}==
<syntaxhighlight lang=text>
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 395 ⟶ 759:
78498+236+1 NB. and we "claimed" that 1 had a prime factor
78735</syntaxhighlight>
 
=={{header|Java}}==
<syntaxhighlight lang="java">
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
 
public final class RadicalOfAnInteger {
 
public static void main(String[] aArgs) {
sievePrimes();
distinctPrimeFactors();
System.out.println("Radical of first 50 positive integers:");
for ( int n = 1; n <= 50; n++ ) {
System.out.print(String.format("%3d%s", radical(n), ( n % 10 == 0 ? "\n" : "" )));
}
System.out.println();
for ( int n : List.of( 99_999, 499_999, 999_999 ) ) {
System.out.println(String.format("%s%7d%s%7d", "Radical for ", n, ":", radical(n)));
}
System.out.println();
System.out.print("Distribution of the first one million positive ");
System.out.println("integers by numbers of distinct prime factors:");
List<Integer> counts = IntStream.rangeClosed(0, 7).boxed().map( i -> 0 ).collect(Collectors.toList());
for ( int n = 1; n <= LIMIT; n++ ) {
counts.set(distinctPrimeFactorCount(n), counts.get(distinctPrimeFactorCount(n)) + 1);
}
for ( int n = 0; n < counts.size(); n++ ) {
System.out.println(String.format("%d%s%7d", n, ":", counts.get(n)));
}
System.out.println();
System.out.println("Number of primes and powers of primes less than or equal to one million:");
int count = 0;
final double logOfLimit = Math.log(LIMIT);
for ( int p : primes ) {
count += logOfLimit / Math.log(p);
}
System.out.println(count);
}
private static int radical(int aNumber) {
return distinctPrimeFactors.get(aNumber).stream().reduce(1, Math::multiplyExact);
}
private static int distinctPrimeFactorCount(int aNumber) {
return distinctPrimeFactors.get(aNumber).size();
}
private static void distinctPrimeFactors() {
distinctPrimeFactors = IntStream.rangeClosed(0, LIMIT).boxed()
.map( i -> new ArrayList<Integer>() ).collect(Collectors.toList());
for ( int p : primes ) {
for ( int n = p; n <= LIMIT; n += p ) {
distinctPrimeFactors.get(n).add(p);
}
}
}
private static void sievePrimes() {
List<Boolean> markedPrime = IntStream.rangeClosed(0, LIMIT).boxed()
.map( i -> true ).collect(Collectors.toList());
for ( int p = 2; p * p <= LIMIT; p++ ) {
if ( markedPrime.get(p) ) {
for ( int i = p * p; i <= LIMIT; i += p ) {
markedPrime.set(i, false);
}
}
}
primes = new ArrayList<Integer>();
for ( int p = 2; p <= LIMIT; p++ ) {
if ( markedPrime.get(p) ) {
primes.add(p);
}
}
}
 
private static List<Integer> primes;
private static List<List<Integer>> distinctPrimeFactors;
private static final int LIMIT = 1_000_000;
 
}
</syntaxhighlight>
{{ out }}
<pre>
Radical of 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
 
Radical for 99999: 33333
Radical for 499999: 3937
Radical for 999999: 111111
 
Distribution of the first one million positive integers by numbers of distinct prime factors:
0: 1
1: 78734
2: 288726
3: 379720
4: 208034
5: 42492
6: 2285
7: 8
 
Number of primes and powers of primes less than or equal to one million:
78734
</pre>
 
=={{header|jq}}==
Line 608 ⟶ 1,087:
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>
 
=={{header|MAD}}==
<syntaxhighlight lang="mad"> NORMAL MODE IS INTEGER
 
INTERNAL FUNCTION(A,B)
ENTRY TO REM.
FUNCTION RETURN A-A/B*B
END OF FUNCTION
 
INTERNAL FUNCTION(NN)
ENTRY TO RADIC.
KN = NN
DPF = 0
RAD = 1
WHENEVER KN.E.0, FUNCTION RETURN 0
WHENEVER REM.(KN,2).E.0
DPF = 1
RAD = 2
THROUGH DIV2, FOR KN=KN, 0, REM.(KN,2).NE.0
DIV2 KN = KN / 2
END OF CONDITIONAL
THROUGH ODD, FOR FAC=3, 2, FAC.G.KN
WHENEVER REM.(KN,FAC).E.0
DPF = DPF + 1
RAD = RAD * FAC
THROUGH DIVP, FOR KN=KN, 0, REM.(KN,FAC).NE.0
DIVP KN = KN / FAC
END OF CONDITIONAL
ODD CONTINUE
FUNCTION RETURN RAD
END OF FUNCTION
 
R PRINT RADICALS FOR 1..50
VECTOR VALUES RADLIN = $10(I5)*$
PRINT COMMENT $ RADICALS OF 1 TO 50$
THROUGH RADL, FOR L=0, 10, L.GE.50
RADL PRINT FORMAT RADLIN,
0 RADIC.(L+1),RADIC.(L+2),RADIC.(L+3),RADIC.(L+4),
1 RADIC.(L+5),RADIC.(L+6),RADIC.(L+7),RADIC.(L+8),
2 RADIC.(L+9),RADIC.(L+10)
 
R PRINT RADICALS OF TASK NUMBERS
PRINT COMMENT $ $
VECTOR VALUES RADNUM = $14HTHE RADICAL OF,I7,S1,2HIS,I7*$
THROUGH RADN, FOR VALUES OF N = 99999, 499999, 999999
RADN PRINT FORMAT RADNUM,N,RADIC.(N)
 
R FIND DISTRIBUTION
PRINT COMMENT $ $
DIMENSION DIST(8)
THROUGH ZERO, FOR D = 0, 1, D.G.7
ZERO DIST(D) = 0
 
THROUGH CNTDST, FOR N = 1, 1, N.G.1000000
RADIC.(N)
CNTDST DIST(DPF) = DIST(DPF) + 1
 
PRINT COMMENT $ DISTRIBUTION OF RADICALS$
VECTOR VALUES DISTLN = $I1,2H: ,I8*$
THROUGH SHWDST, FOR D = 0, 1, D.G.7
SHWDST PRINT FORMAT DISTLN,D,DIST(D)
 
END OF PROGRAM</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
 
THE RADICAL OF 99999 IS 33333
THE RADICAL OF 499999 IS 3937
THE RADICAL OF 999999 IS 111111
 
DISTRIBUTION OF RADICALS
0: 1
1: 78734
2: 288726
3: 379720
4: 208034
5: 42492
6: 2285
7: 8</pre>
 
=={{header|Nim}}==
Line 1,459 ⟶ 2,091:
 
Real time: 15.218 s User time: 15.068 s Sys. time: 0.033 s CPU share: 99.23 %
</pre>
 
=={{header|PascalABC.NET}}==
<syntaxhighlight lang="delphi">
function Factors(N: integer): List<integer>;
begin
var lst := new List<integer>;
var i := 2;
while i * i <= N do
begin
while N.Divs(i) do
begin
if i not in lst then
lst.Add(i);
N := N div i;
end;
i += 1;
end;
if N >= 2 then
lst.Add(N);
Result := lst;
end;
 
function Radical(x: integer) := Factors(x).Product;
 
begin
for var i:=1 to 50 do
begin
Write(Radical(i):3);
if i mod 10 = 0 then
Writeln;
end;
Writeln;
 
Writeln('Radical(99999) = ',Radical(99999));
Writeln('Radical(499999) = ',Radical(499999));
Writeln('Radical(999999) = ',Radical(999999));
Writeln;
 
var a := |0| *8;
for var i:=1 to 1000000 do
a[Factors(i).Count] += 1;
for var i:=0 to 7 do
Writeln($'{i}: {a[i]}');
end.
</syntaxhighlight>
{{out}}
<pre>
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(99999) = 33333
Radical(499999) = 3937
Radical(999999) = 111111
 
0: 1
1: 78734
2: 288726
3: 379720
4: 208034
5: 42492
6: 2285
7: 8
</pre>
 
 
=={{header|Perl}}==
{{libheader|ntheory}}
<syntaxhighlight lang="perl" line>
use strict;
use warnings;
use feature <say signatures>;
no warnings 'experimental::signatures';
 
use List::Util 'uniq';
use ntheory <primes vecprod factor>;
 
sub comma { reverse ((reverse shift) =~ s/.{3}\K/,/gr) =~ s/^,//r }
sub table (@V) { ( sprintf( ('%3d')x@V, @V) ) =~ s/.{1,30}\K/\n/gr }
 
sub radical ($n) { vecprod uniq factor $n }
 
my $limit = 1e6;
 
my $primes = primes(1,$limit);
 
my %rad;
$rad{1} = 1;
$rad{ uniq factor $_ }++ for 2..$limit;
 
my $powers;
my $upto = int sqrt $limit;
for my $p ( grep { $_< $upto} @$primes ) {
for (2..$upto) { ($p ** $_) < $limit ? ++$powers : last }
}
 
say 'First fifty radicals:';
say table map { radical $_ } 1..50;
printf "Radical for %7s => %7s\n", comma($_), comma radical($_) for 99999, 499999, 999999;
printf "\nRadical factor count breakdown, 1 through %s:\n", comma $limit;
say "$_ => " . comma $rad{$_} for sort keys %rad;
say <<~"END";
 
Up to @{[comma $limit]}:
Primes: @{[comma 0+@$primes]}
Powers: $powers
Plus 1: 1
Total: @{[comma 1 + $powers + @$primes]}
END
</syntaxhighlight>
{{out}}
<pre>
First fifty radicals:
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 for 99,999 => 33,333
Radical for 499,999 => 3,937
Radical for 999,999 => 111,111
 
Radical factor count breakdown, 1 through 1,000,000:
1 => 78,735
2 => 288,726
3 => 379,720
4 => 208,034
5 => 42,492
6 => 2,285
7 => 8
 
Up to 1,000,000:
Primes: 78,498
Powers: 236
Plus 1: 1
Total: 78,735
</pre>
 
Line 1,508 ⟶ 2,280:
[[File_size_distribution#Phix|here]], or
[[Numbers_k_such_that_the_last_letter_of_k_is_the_same_as_the_first_letter_of_k%2B1#Phix|here]].
=={{header|Python}}==
<syntaxhighlight lang="Python">
# int_radicals.py by Xing216
 
def radical(n):
product = 1
if (n % 2 == 0):
product *= 2
while (n%2 == 0):
n = n/2
for i in range (3, int((n)**0.5), 2):
if (n % i == 0):
product = product * i
while (n%i == 0):
n = n/i
if (n > 2):
product = product * n
return int(product)
def distinctPrimeFactors(N):
factors = []
if (N < 2):
factors.append(-1)
return factors
if N == 2:
factors.append(2)
return factors
visited = {}
i = 2
while(i * i <= N):
while(N % i == 0):
if(i not in visited):
factors.append(i)
visited[i] = 1
N //= i
i+=1
if(N > 2):
factors.append(N)
return factors
if __name__ == "__main__":
print("Radical of first 50 positive integers:")
for i in range(1,51):
print(f"{radical(i):>2}", end=" ")
if (i % 10 == 0):
print()
print()
for n in [99999, 499999, 999999]:
print(f"Radical of {n:>6}: {radical(n)}")
distDict = {1:0,2:0,3:0,4:0,5:0,6:0,7:0}
for i in range(1,1000000):
distinctPrimeFactorCount = len(distinctPrimeFactors(i))
distDict[distinctPrimeFactorCount] += 1
print("\nDistribution of the first one million positive integers by numbers of distinct prime factors:")
for key, value in distDict.items():
print(f"{key}: {value:>6}")
print("\nNumber of primes and powers of primes less than or equal to one million:")
print(distDict[1])
</syntaxhighlight>
{{out}}
<pre>
Radical of first 50 positive integers:
1 2 3 2 5 6 7 2 9 10
11 6 13 14 15 2 17 18 19 10
21 22 23 6 25 26 3 14 29 30
31 2 33 34 35 18 37 38 39 10
41 42 43 22 15 46 47 6 49 50
 
Radical of 99999: 33333
Radical of 499999: 3937
Radical of 999999: 111111
 
Distribution of the first one million positive integers by numbers of distinct prime factors:
1: 78735
2: 288725
3: 379720
4: 208034
5: 42492
6: 2285
7: 8
 
Number of primes and powers of primes less than or equal to one million:
78735
</pre>
=={{header|Raku}}==
 
Line 1,574 ⟶ 2,427:
Total: 78,735
</pre>
=={{header|REXX}}==
===Version 1===
<syntaxhighlight lang="rexx">
/* REXX */
arg n
if n = '' then
n = 1000000
Numeric Digits 100
parse version version; say version digits() 'Digits'
say 'Radical of an integer = product of distinct prime factors'
say 'Version 1: tailor-made routines'
say
call setp
/* 1. Radicals from 1 to 50 */
Say 'Radicals of 1..50:'
ol=''
Do i=1 To 50
ol=ol||right(rad(i),5)
If i//10=0 then Do
Say ol
ol=''
End
End
 
Say ''
Call radt 99999
Call radt 499999
Call radt 999999
Say ''
Say 'Distribution of radicals:'
cnt.=0
m = n/10
Say ''
Say 'Getting distribution list...'
Call time 'R'
Do v=1 To n
p=rad(v,'cnt')
cnt.p+=1
If v//m=0 Then Do
ti=(v%m)*10
say format(ti,3)'%' format(time('E'),4,3) 'seconds'
End
/**************************************
If p=7 Then
Say v':' rad(v,'lstx') '=' rad(v)
**************************************/
End
Say ''
Say 'Results'
Do d=0 To 20
If cnt.d>0 Then
Say d':' right(cnt.d,8)
End
exit
 
radt:
Parse Arg u
Say 'The radical of' u 'is' rad(u)'.'
Return
 
rad:
Parse Arg z,what
zz=z
plist=''
exp.=0
Do Until p*p>z
Do pi=1 By 1 Until p*p>z
p=word(primzahlen,pi)
exp.p=0
Do while z//p=0
exp.p+=1
If pos(p,plist)=0 Then
plist=plist p
z=z%p
End
End
End
exp.z+=1
If pos(z,plist)=0 &z<>1 Then
plist=plist z
Select
When what='lst' Then
Return plist
When what='lstx' Then Do
s=''
Do While plist<>''
Parse Var plist p plist
if exp.p=1 Then
s=s'*'p
Else
s=s'*'p'**'exp.p
End
Return strip(s,,'*')
End
When what='cnt' Then
Return words(plist)
Otherwise Do
rad=1
Do while plist>''
Parse Var plist p plist
rad=rad*p
End
Return rad
End
End
 
setp:
primzahlen=,
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101,
103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197,
199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311,
313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431,
433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557,
563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661,
673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809,
811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937,
941 947 953 967 971 977 983 991 997 1009 1013 1019 1021 1031 1033 1039 1049
Return
</syntaxhighlight>
{{out}}
<pre>
REXX-ooRexx_5.0.0(MT)_64-bit 6.05 23 Dec 2022 100 Digits
Radical of an integer = product of distinct prime factors
Version 1: tailor-made routines
 
Radicals of 1..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
 
The radical of 99999 is 33333.
The radical of 499999 is 3937.
The radical of 999999 is 111111.
 
Distribution of radicals:
 
Getting distribution list...
10% 2.747 seconds
20% 6.474 seconds
30% 10.712 seconds
40% 15.524 seconds
50% 20.787 seconds
60% 26.516 seconds
70% 32.870 seconds
80% 39.696 seconds
90% 46.792 seconds
100% 54.265 seconds
 
Results
0: 1
1: 78734
2: 288726
3: 379720
4: 208034
5: 42492
6: 2285
7: 8
</pre>
This program is optimized for the task (all primes up to 1000 are specified...) and works to n = 1000000 max.
===Libraries===
REXX does not have an 'include' facility nor 'arbitrary precision' mathematical functions out of the
box. In previous REXX entries it was custom the have all needed routines or procedures copied into
the program. Newer entries redirect to<br>
[[Mathematics.rex|Libraries]] and<br>
[[Compiler/Simple file inclusion pre processor#rexx|Pre processor and Include clause]].<br>
At the end of each entry you'll find several 'Include' clauses, showing the libraries that the program
needs (cf '#include', 'import', 'uses' or '::requires').
===Version 2===
Below program uses generic optimized procedures for checking and finding factors and primes. It will work for any n (but for say n > 2000000 it becomes very slow).
<syntaxhighlight lang="rexx">
/* REXX */
arg n
if n = '' then
n = 1000000
numeric digits 100
parse version version; say version digits() 'Digits'
say 'Radical of an integer = product of distinct prime factors'
say 'Version 2: using generic procedures'
say
say 'Radicals for 1..50:'
ol = ''
do i = 1 to 50
ol = ol||Right(Radical(i),5)
if i//10 = 0 then do
say ol; ol = ''
end
end
say
say 'Radicals for:'
say '99999 =' Radical(99999)
say '499999 =' Radical(499999)
say '999999 =' Radical(999999)
say
m = n/10; r = ISqrt(n); radi. = 0; glob. = ''
say 'Getting distribution list...'
call Time('r')
do i = 1 to n
call Radical(i)
u = glob.ufactor.0
radi.u = radi.u+1
if i//m=0 then do
ti=(i%m)*10
say format(ti,3)'%' format(time('e'),4,3) 'seconds'
end
end
say
say 'Distribution for first' n 'radicals over number of factors:'
do i = 0 to 10
if radi.i > 0 then
say Right(i,2)':' Right(radi.i,6)
end
say
say 'Getting primes up to' n'...'
call Time('r')
pr = Primes(n)
say 'Took' Format(Time('e'),,3) 'seconds'
say
say 'Getting powers of primes up to' r'...'
call Time('r')
pw = 0
do i = 1
p1 = glob.prime.i
if p1 > r then
leave
p2 = p1
do forever
p2 = p2*p1
if p2 > n then
leave
pw = pw+1
end
end
say 'Took' Format(Time('e'),,3) 'seconds'
say
say 'Primes' Format(pr,6)
say 'Powers' Format(pw,6)
say ' -----'
say 'Total ' Format(pr+pw,6)
exit
 
Radical:
/* Radical function = product of unique prime factors */
procedure expose glob.
arg x
/* Validity */
if \ Whole(x) then
return 'X'
if x < 1 then
return 'X'
/* Get (unique) factors */
n = Factors(x)
/* Calculate product */
y = 1
do i = 1 to glob.ufactor.0
y = y*glob.ufactor.i
end
return y
 
include Functions
include Numbers
</syntaxhighlight>
{{out}}
<pre>
REXX-ooRexx_5.0.0(MT)_64-bit 6.05 23 Dec 2022 100 Digits
Radical of an integer = product of distinct prime factors
Version 2: using generic procedures
 
Radicals for 1..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
 
Radicals for:
99999 = 33333
499999 = 3937
999999 = 111111
 
Getting distribution list...
10% 2.581 seconds
20% 5.628 seconds
30% 9.254 seconds
40% 12.769 seconds
50% 16.457 seconds
60% 20.223 seconds
70% 24.439 seconds
80% 28.736 seconds
90% 33.197 seconds
100% 37.532 seconds
 
Distribution for first 1000000 radicals over number of factors:
0: 1
1: 78734
2: 288726
3: 379720
4: 208034
5: 42492
6: 2285
7: 8
 
Getting primes up to 1000000...
Took 0.909 seconds
 
Getting powers of primes up to 1000...
Took 0.000 seconds
 
Primes 78498
Powers 236
-----
Total 78734
</pre>
Version 2 is slightly faster than Version 1.
 
=={{header|RPL}}==
Line 1,649 ⟶ 2,817:
 
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 1,655 ⟶ 2,899:
{{libheader|Wren-seq}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="ecmascriptwren">import "./math" for Int, Nums
import "./seq" for Lst
import "./fmt" for Fmt
Retrieved from "https://rosettacode.org/wiki/Radical_of_an_integer"