Все числа с ровно 8 делителями

Question

Учитывая 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 <= num; ++i) { 
     count = 0; 
     while (num % i == 0) { 
      count++; 
      num /= i; 
     } 
     ans *= (count + 1); 
     if (ans > 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?

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

Answer 1

Все дело в том, чтобы найти число чисел, а не числа, которые уменьшают проблему от итераций до вычислений.

Для числа, имеющего 8 делителей, оно должно быть либо записано в одной из трех форм.

p1 * p2 * p3 

p1^3 * p2 

p^7 

потому, что из формулы 8 = 2 * 2 * 2 or 4 * 2 or 8 * 1

Так что если мы знаем, сколько простых чисел ниже n, мы можем выяснить, комбинации, которые могут иметь 8 делителей.

p1*p2*p3: 

The maximum `p` can be `N/2 * 3`. 
So the number of numbers which have `8` divisors are nC3. 

p1^3*p2: 

The maximum `p` can be `N/8`. 
So the number of numbers which have `8` divisors are nC2. 

p^7: 

The maximum `p` can be `N^(1/7)`. 
So the number of numbers which have `8` divisors are `n`. 

Here, `n` is the number of primes under `N` 

Таким образом, чтобы узнать n количество простых чисел под N, мы можем использовать Prime Counting Function вместо вычисления простых чисел.

Итак, как только вы знаете количество простых чисел, вы можете рассчитать количество чисел по селективным комбинациям.