Все числа, имеющие ровно 8 делителей ⇐ JAVA

[Anonymous]

Дано n, мне нужно количество чисел, имеющих ровно 8 делителей.

Код: Выделить всё

24 = 1, 2, 3, 4, 6, 8, 12, 24

Ниже 100 есть 10 чисел, удовлетворяющих вышеуказанному условию.

Код: Выделить всё

24, 30, 40, 42, 54, 56, 66, 70, 78 and 88

.

При n, сколько чисел удовлетворяют указанному выше условию ниже n.

Первый подход:

Я использовал подход с простыми множителями.

Код: Выделить всё

x = p1^k1 * p2 ^k2 * p3^k3 ...
n = (k1 + 1)(k2 + 1)(k3 + 1)...

Этот подход немного медленный при работе с большими числами.

Код: Выделить всё

int max = 1000000000;
int count = 0;
for(int i = 0; i < max; ++i)
if(check(i))count++;

private static boolean check(int num) {
int ans = 1;
int count = 0;
while (num % 2 == 0) {
num /= 2;
count++;
}
ans *= (count + 1);
if (ans > 8)
return false;
for (int i = 3; i * i  8)
return false;
}
if (num != 1)
ans *= 2;
if (ans > 8)
return false;
return ans == 8;
}

Второй подход:

аналогичный метод просеивания, который отмечает все кратные числа, а затем проверяет, равно ли число 8 или нет.

Код: Выделить всё

static int max = 100000000;
static int[] facs = new int[max];

for (int i = 2; i < max; ++i) {
for (int j = i; j < max; j += i) {
facs[j]++;
}
}
int count = 0;
for (int i = 0; i < max; ++i)
if (facs[i] == 7)//1 is a factor of all number so check for count 7
count++;
System.out.println(count);

Однако этот подход немного быстрее, но его нельзя использовать для больших чисел выше 10^9.

Как вычислить числа, у которых ровно 8 делителей больше 10^9?

Есть ли какой-нибудь трюк, который мне не хватает? Как я могу это улучшить?