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

Question

это актуальный вопрос

однако он упрощается до

Найти все ПОЛУПРИЦЫ (числа, которые произведение 2-х DISTINCT простых множителей, например, 6 (2 * 3) в диапазоне от L до R

, будет несколько запросов для L и R

, мы не можем предварительно вычислить полупростые числа, так как N большое

НО мы можем хранить простые числа, поскольку они только до 10 ^ 6 согласно вопросу

Теперь предположим, что у меня есть все простые числа по сите Eratostheneses

Мне нужны все возможные пары простых чисел с продуктом от L до R

ИЛИ ПРОСТО ПРОСТО ДАТЬ ДАННУЮ Массив. НАЙТИ ВСЕ ВОЗМОЖНЫЕ ПАРЫ С ПРОДУКТАМИ МЕЖДУ L & R INCLUSIVE

Я включаю часть кода в редакционную статью, которая делает это ..

for(int i=0; i<cnt and ar[i]<=r; i++)
{
    int lower = L/ar[i];
    if(L%ar[i]>0)
        lower++;
    lower = max(lower, ar[i]+1);
    int upper = R/ar[i];
    if(upper<lower)
        continue;
    ans += upper_bound(ar.begin(),ar.end(),upper)-
            lower_bound(ar.begin(),ar.end(),lower);
}

Answer 1

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

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

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

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

Уже есть генеративный процесс для Семпраймов. Каждый полупростой является продуктом двух различных простых факторов.

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

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

Мы можем немного модифицировать сито Эратосфена для генерации полупростых.

Идея в том, что мы будем хранить массив 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). Если (RL) <10 ^ 5, этот подход пройдет. Но поскольку (RL) может достигать 10 ^ 8, это невозможно. </p>

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

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

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 не отличаются (р, д должны быть разными). Но, 3 входит, как 2 * 3 <= 10, так и 5, 2 * 5 2 * 5 <= 10. </p>

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

Мы возьмем нижнюю ограниченный как 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)) на запрос.