114 lines
3.4 KiB
Java
114 lines
3.4 KiB
Java
import java.util.*;
|
|
import java.io.*;
|
|
|
|
public class UntouchableNumbers {
|
|
|
|
static int sumDivisors(int n) {
|
|
int sum = 1;
|
|
int k = 2;
|
|
if (n % 2 == 0) {
|
|
k = 1;
|
|
}
|
|
for (int i = 1 + k; (long) i * i <= n; i += k) {
|
|
if (n % i == 0) {
|
|
sum += i;
|
|
int j = n / i;
|
|
if (j != i) {
|
|
sum += j;
|
|
}
|
|
}
|
|
}
|
|
return sum;
|
|
}
|
|
|
|
// Marks as true the integers that appear as a proper-divisor sum of some i (6..n+1).
|
|
static boolean[] sieve(int n) {
|
|
int m = n + 1; // mirror the Go code's n++ trick
|
|
boolean[] s = new boolean[m + 1]; // all false by default
|
|
for (int i = 6; i <= m; i++) {
|
|
int sd = sumDivisors(i);
|
|
if (sd <= m) {
|
|
s[sd] = true;
|
|
}
|
|
}
|
|
return s;
|
|
}
|
|
|
|
// True = composite, False = prime (like the Go version)
|
|
static boolean[] primeSieve(int limit) {
|
|
int lim = limit + 1;
|
|
boolean[] c = new boolean[lim];
|
|
c[0] = true;
|
|
c[1] = true;
|
|
int p = 3;
|
|
while (true) {
|
|
long p2 = (long) p * p;
|
|
if (p2 >= lim) break;
|
|
for (int i = (int) p2; i < lim; i += 2 * p) {
|
|
c[i] = true;
|
|
}
|
|
while (true) {
|
|
p += 2;
|
|
if (p >= lim || !c[p]) break;
|
|
}
|
|
if (p >= lim) break;
|
|
}
|
|
return c;
|
|
}
|
|
|
|
static String commatize(long n) {
|
|
boolean neg = n < 0;
|
|
String s = Long.toString(Math.abs(n));
|
|
StringBuilder sb = new StringBuilder();
|
|
int le = s.length();
|
|
int first = le % 3;
|
|
if (first == 0 && le > 0) first = 3;
|
|
sb.append(s, 0, first);
|
|
for (int i = first; i < le; i += 3) {
|
|
if (sb.length() > 0) sb.append(',');
|
|
sb.append(s, i, i + 3);
|
|
}
|
|
return neg ? "-" + sb : sb.toString();
|
|
}
|
|
|
|
public static void main(String[] args) {
|
|
final int limit = 10_000;
|
|
|
|
boolean[] composite = primeSieve(limit);
|
|
boolean[] sumsSeen = sieve(63 * limit);
|
|
|
|
List<Integer> untouchable = new ArrayList<>();
|
|
untouchable.add(2);
|
|
untouchable.add(5);
|
|
|
|
for (int n = 6; n <= limit; n += 2) {
|
|
if (!sumsSeen[n] && composite[n - 1] && composite[n - 3]) {
|
|
untouchable.add(n);
|
|
}
|
|
}
|
|
|
|
System.out.println("List of untouchable numbers <= 2,000:");
|
|
int count = 0;
|
|
for (int i = 0; i < untouchable.size() && untouchable.get(i) <= 2000; i++) {
|
|
System.out.printf("%6s", commatize(untouchable.get(i)));
|
|
if ((i + 1) % 10 == 0) System.out.println();
|
|
count++;
|
|
}
|
|
System.out.printf("%n%n%7s untouchable numbers were found <= 2,000%n", commatize(count));
|
|
|
|
int p = 10;
|
|
count = 0;
|
|
for (int n : untouchable) {
|
|
count++;
|
|
if (n > p) {
|
|
System.out.printf("%7s untouchable numbers were found <= %9s%n",
|
|
commatize(count - 1), commatize(p));
|
|
p *= 10;
|
|
if (p == limit) break;
|
|
}
|
|
}
|
|
|
|
System.out.printf("%7s untouchable numbers were found <= %s%n",
|
|
commatize(untouchable.size()), commatize(limit));
|
|
}
|
|
}
|