Radical of an integer: Difference between revisions
Content added Content deleted
(Added C++ solution) |
(New post.) |
||
Line 622: | Line 622: | ||
78498+236+1 NB. and we "claimed" that 1 had a prime factor |
78498+236+1 NB. and we "claimed" that 1 had a prime factor |
||
78735</syntaxhighlight> |
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}}== |
=={{header|jq}}== |