Найдите количество пар в массиве с произведением между l и r включительно

Вот один из подходов, это может быть не быстрее, но кажется разумным.

1. Количество простых чисел ниже 10 ^ 8 составляет около 5 * 10 ^ 6.

ссылка: https://en.wikipedia.org/wiki/Prime-counting_function

2. Но нам, возможно, не придется сохранять все простые числа, так как это было бы довольно неэффективно. Мы можем оставить только полупростые числа.

Генеративный процесс для Semprimes уже существует. Каждое полупростое число является произведением двух различных простых множителей.

Итак, мы можем сохранить массив, в котором будут храниться все полупростые числа, поскольку в диапазоне будет не более 10 ^ 5 полупростых чисел, мы можем отсортировать этот массив. Для каждого запроса мы будем просто выполнять двоичный поиск в массиве, чтобы найти количество элементов в диапазоне.

3. Итак, как сохранить полупростые числа?

Мы можем немного модифицировать решето Эратосфена, чтобы генерировать полупростые числа.

Идея состоит в том, что мы будем хранить массив countDivision, в котором будет храниться число делителей для каждого целого числа в диапазоне. Мы рассматриваем только целое полупростое число, если countDivision значение индекса равно 2 для этого целого числа (2 делителя).

def createSemiPrimeSieve(n): 
    v = [0 for i in range(n + 1)] 

    # This array will initially store the indexes 
    # After performing below operations if any 
    # element of array becomes 1 this means 
    # that the given index is a semi-prime number 

    # Storing indices in each element of vector 
    for i in range(1, n + 1): 
        v[i] = i 

    countDivision = [0 for i in range(n + 1)] 

    for i in range(n + 1): 
        countDivision[i] = 2

    # This array will initially be initialized by 2 and 
    # will just count the divisions of a number 
    # As a semiprime number has only 2 prime factors 
    # which means after dividing by the 2 prime numbers 
    # if the index countDivision[x] = 0 and v[x] = 1 
    # this means that x is a semiprime number 

    # If number a is prime then its 
    # countDivision[a] = 2 and v[a] = a 

    for i in range(2, n + 1, 1): 

        # If v[i] != i this means that it is 
        # not a prime number as it contains 
        # a divisor which has already divided it 
        # same reason if countDivision[i] != 2 
        if (v[i] == i and countDivision[i] == 2): 

            # j goes for each factor of i 
            for j in range(2 * i, n + 1, i): 
                if (countDivision[j] > 0): 

                    # Dividing the number by i 
                    # and storing the dividend 
                    v[j] = int(v[j] / i) 

                    # Decreasing the countDivision 
                    countDivision[j] -= 1

    # A new vector to store all Semi Primes 
    res = [] 

    for i in range(2, n + 1, 1): 

        # If a number becomes one and 
        # its countDivision becomes 0 
        # it means the number has 
        # two prime divisors 
        if (v[i] == 1 and countDivision[i] == 0): 
            res.append(i) 

    return res 

Кредит: https://www.geeksforgeeks.org/print-all-semi-prime-numbers-less-than-or-equal-to-n/

Но генерация имеет ту же сложность, что и решето, которое равно O(nloglogn). Если (R-L) ‹ 10 ^ 5, этот подход пройдет. Но поскольку (RL) может достигать 10 ^ 8, это невозможно.

Другой подход заключается в подсчете вместо генерации.

Давайте поработаем на примере.

2 10

Теперь, скажем, мы знаем все простые числа до 10^6 (поскольку p и q не могут быть больше 10^6).

primes = [2, 3, 5, 7, 11, ...]

Количество простых чисел ниже 10 ^ 6 меньше 10 ^ 5 (поэтому мы можем хранить их в массиве), и временная сложность также управляема.

Теперь мы можем просмотреть наш массив primes, чтобы подсчитать вклад каждого простого числа для создания полупростых чисел в диапазоне (L, R).

Во-первых, начнем с 2, сколько полупростых чисел мы сгенерируем с помощью 2.

Давайте посмотрим на простые числа = [2, 3, 5, 7, 11, ..]

Мы не можем выбрать 2, потому что 2 и 2 не различны (p, q должны быть разными). Но 3 входит, как 2*3 ‹= 10, так и 5, 2*5 2*5 ‹= 10.

Как это посчитать?

Мы возьмем нижнюю границу как 2//2 (L//primes[i]), но мы должны убедиться, что мы не рассматриваем текущее простое число снова как (p и q должны быть разными), поэтому мы берем максимум из L//primes[i] и primes[i]+1.

Для 2 наше начальное число равно 3 (поскольку 2 + 1 = 3, мы не можем начать с 1 или 2, так как если мы рассматриваем 2, мы будем вычислять такие случаи, как 2 * 2 = 4, что неверно). Наше конечное число 10//2 = 5, сколько чисел находится в пределах диапазона 3, 5 в простых числах. Это 2, и его можно найти с помощью простого двоичного поиска.

Остальное легко, нам придется бинарно искать, сколько простых чисел находится в диапазоне (max(L//primes[i], primes[i]+1), R//primes[i]).

Это имеет сложность предварительной обработки сложности времени O (10 ^ 6 * loglog (10 ^ 6)) + O (10 ^ 6 * log (10 ^ 6)) и O (log (10 ^ 6)) на запрос.