Radical of an integer: Difference between revisions
m
→{{header|ALGOL 68}}: Fixed note about specifying the heap size
SqrtNegInf (talk | contribs) (Added Perl) |
m (→{{header|ALGOL 68}}: Fixed note about specifying the heap size) |
||
| (9 intermediate revisions by 6 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)
Line 335 ⟶ 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 496 ⟶ 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 708 ⟶ 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 1,766 ⟶ 2,213:
[[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,832 ⟶ 2,360:
Total: 78,735
</pre>
=={{header|
<syntaxhighlight lang="rexx">
/* REXX */
Line 1,978 ⟶ 2,506:
9 83.6 seconds
10 100.6 seconds</pre>
=={{header|RPL}}==
Line 2,055 ⟶ 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,061 ⟶ 2,663:
{{libheader|Wren-seq}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="
import "./seq" for Lst
import "./fmt" for Fmt
| |||