86 lines
2.7 KiB
Java
86 lines
2.7 KiB
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;
|
|
|
|
}
|