Semiprimos libres de cuadrados en un rango dado usando C++ STL

Dados dos enteros L y R (L < = R). La tarea es encontrar todos los semiprimos libres de cuadrados en el rango L a R (ambos inclusive).

Ejemplos:

Entrada: L = 1, R = 10
Salida: 2
4, 6, 9, 10 son semiprimos. Pero 6, 10 son semiprimos sin cuadrados.

Entrada: L = 10, R = 20
Salida: 3

Prerrequisitos: Tamiz de Eratóstenes , límite superior e inferior

Comprensión:
los semiprimos son números de la forma $p*q$ en que p y q son primos, no necesariamente distintos. Todo semiprimo $n$ tiene solo 4 factores $1, p, q, p*q$ donde p y q son los únicos dos factores primos y $p*q = n$ .

Enfoque ingenuo:
precalcule todos los números primos hasta $\sqrt{R}$ . Encuentre todas las combinaciones de dos primos p y q tales que $p*q = n$ estén entre L y R . Iterar a través de todas las combinaciones de números primos daría una complejidad de tiempo de $O(N $^2$)$ . Esta solución, sin embargo, no funcionará para valores grandes de L y R.

Complejidad del tiempo: O(N^2)

Enfoque eficiente:
precalcule todos los números primos hasta $\sqrt{R}$ . Podemos dividir el problema de encontrar dos números primos p y q en una forma más simple.
Como $L $\leq$p*q$ podemos decir eso $\frac{L}{p} $\leq$q$ . Del mismo modo $p*q $\leq$R$ que podemos decir que $q $\leq$$\frac{R}{p}$ .
Ahora el problema se reduce a encontrar la cuenta de q tal que $\frac{L}{p} $\leq$q $\leq$$\frac{R}{p}$ para todo p.

Aquí, podemos usar la búsqueda binaria para encontrar el límite superior de la $\frac{R}{p}$ lista de números primos y restarlo del índice del límite inferior de la $\frac{L}{p}$ lista de números primos para encontrar el conteo de todos los q en el rango $\frac{L}{p}$ para el p $\frac{R}{p}$ dado . Repetir el paso anterior para todos los primos p dará la respuesta para el rango dado L a R

A continuación se muestra la implementación del enfoque anterior:

// CPP program to find square free semiprimes in the range
#include <bits/stdc++.h>
using namespace std;
  
#define N 78498
  
void Sieve(int pre[])
{
    // Max size of prime array
    int MX = 1e6;
  
    // Array of prime of size 1000001.
    // will be marked true for prime, false otherwise
    // i     = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...]
    // prime = {0, 0, 1, 1, 0, 1, 0, 1, 0, 0, ...}
    bool prime[MX + 1];
  
    // i -> keeps track of index of prime 
    // (current integer)
    // idx -> keeps track of index of pre
    int i = 2;
    int idx = 0;
  
    // Initialize all entries to true
    memset(prime, true, sizeof(prime));
  
    // For all i from 2 to MX iterate
    for (i = 2; i <= MX; i++)
    {
        // If i is prime
        if (prime[i]) 
        {
            // Set idx'th index of pre as i and 
            // increment idx after setting the value
            pre[idx++] = i;
  
            // For all multiple of i from 2*i to MX
            // mark them as false i.e. not prime
            for (int j = (i << 1); j <= MX; j += i)
                prime[j] = false;
        }
    }
}
  
// Function to find square free semi primes in the range
int semiPrimeCount(int L, int R)
{
  
    // Array of prime integer
    // will contain first 78498 primes
    // idx = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...]
    // pre = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ...}
    int pre[N];
  
    // Prepare pre array
    Sieve(pre);
  
    // Result of current query
    int res = 0;
  
    // Offset index from start
    int j = 1;
  
    // For all prime integers p in pre 
    // from 2 to sqrt(R) iterate
    for (auto p : pre) {
        // ub_num     = count of all multiple of p less 
        //             than R => p = R/p
        //
        // ub     = iterator of first element greater 
        //         than ub_num in pre
        //
        int ub_num = R / p;
        auto ub = upper_bound(pre + j, pre + N, ub_num);
  
        // lb_num     = count of all multiple of p 
        //             less than L => p = L/p
        // If L is divisible by p increment p by 
        // 1 => p = p+1 = p+(L%p>0)
        //
        // lb     = iterator of first element greater 
        //         than or equal lb_num in pre
      
        int lb_num = (L / p) + ((L % p) > 0);
        auto lb = lower_bound(pre + j, pre + N, lb_num);
  
        // Add the difference between ub and lb
        res += ub - lb;
  
        // Increment j
        j++;
  
        // If prime p is greater than or equal to sqrt(R)
        if (p * p >= R)
            break;
    }
    return res;
}
  
// Driver code
int main()
{
    int L = 10, R = 20;
      
    // Function call
    cout << semiPrimeCount(L, R);
  
    return 0;
}

Producción:

Complejidad de tiempo: O(N*logN)

Publicación traducida automáticamente

Artículo escrito por NIKHILLONDHE y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta Cancelar la respuesta