Conteo de números hasta N que tienen solo 4 factores o divisores

Dado un número entero N , encuentre el número de números naturales menores o iguales a N y tenga 4 factores.

Ejemplo: 

Entrada: N = 8
Salida: 2
Explicación: {1} es un conjunto de divisores de 1
{1, 2} es un conjunto de divisores de 2
{1, 3} es un conjunto de divisores de 3
{1, 2, 4} es un conjunto de divisores de 4
{1, 5} es un conjunto divisor de 5
{1, 2, 3, 6} es un conjunto divisor de 6
{1, 7} es un conjunto divisor de 7
{1, 2, 4, 8} es un conjunto divisor de 8
Entonces, 6 y 8 son solo números naturales menores o iguales a N y número de divisores 4.

Entrada: N = 2
Salida: 0

Planteamiento: La idea para resolver el problema se basa en la siguiente observación:

• Cualquier número M se puede escribir en la forma M = p ₁ ^e1 * p ₂ ^e2 * . . . donde (p ₁ , p ₂ . . .) son números primos y (e ₁ , e ₂ . . .) son exponentes respectivos.
• El número total de factores de M es por lo tanto (e + 1)*(e + 1)* . . .
• De los puntos anteriores, para que la cuenta de divisores de un número natural sea 4, hay dos casos:
  • Caso-1 : N = p1 * p2 (donde p1 y p2 son dos números primos distintos)
  • Caso-2 : N = p ³ (donde p es un número primo)
• Entonces debe haber dos primos cuya multiplicación sea menor que N o un primo cuyo cubo sea menor que N.

Siga los pasos que se mencionan a continuación para resolver el problema:

• Encuentra todos los números primos menores o iguales a N usando la criba de Eratóstenes .
• Para el Caso-1, itere a través de todos los números primos y use la búsqueda binaria para encontrar un número de números primos cuyo producto sea N como máximo .
• Para el Caso-2 , realice una búsqueda binaria para encontrar el número de números primos cuyo cubo sea menor o igual que N.

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

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find primes <= N
vector<int> SieveOfEratosthenes(int n)
{
    // Create a boolean array
    // "prime[0..n]" and initialize
    // all entries it as true.
    // A value in prime[i] will
    // finally be false if i is
    // Not a prime, else true.
    bool prime[n + 1];
    memset(prime, true, sizeof(prime));
 
    for (long long int p = 2;
         p * p <= n; p++) {
 
        // If prime[p] is not changed,
        // then it is a prime
        if (prime[p] == true) {
            // Update all multiples
            // of p greater than or
            // equal to the square of it
            for (long long int i = p * p;
                 i <= n; i += p)
                prime[i] = false;
        }
    }
 
    // Vector for storing prime number
    // less than or equal to N
    vector<int> primes;
 
    // Store all prime numbers
    for (int p = 2; p <= n; p++)
        if (prime[p])
            primes.push_back(p);
 
    return primes;
}
 
// Find floor of cube root of N
int primeCubic(vector<int>& primes, int N)
{
 
    // Val stores cube root of N
    long long int l = 0, r = N, mid, val;
 
    // Binary search loop for finding
    // floor of cube root of N
    while (l <= r) {
        mid = (l + r) / 2;
        if ((mid * mid * mid) <= N) {
            val = mid;
            l = mid + 1;
        }
        else {
            r = mid - 1;
        }
    }
 
    // Iterator for finding index with
    // value just greater than Val in primes
    auto it = upper_bound(primes.begin(),
                          primes.end(), val);
    it--;
 
    return (it - primes.begin() + 1);
}
 
// Function to find primes with product <= N
int primeProduct(vector<int>& primes,
                 int N)
{
    // Stores the answer
    int answer = 0;
 
    // Iterator storing pointer to
    // current prime
    auto cur = primes.begin();
 
    // Loop for traversing all primes
    // Find number of indices less than
    // current indices for which product
    // is less than or equal to N
    for (auto i : primes) {
        long long int add
            = upper_bound(primes.begin(),
                          cur, (N / i))
              - primes.begin();
        answer += add;
        cur++;
    }
    return answer;
}
 
// Function to find the total count
int print(int N)
{
    vector<int> primes
        = SieveOfEratosthenes(N);
 
    int answer = 0;
    answer += primeCubic(primes, N);
    answer += primeProduct(primes, N);
    return answer;
}
 
// Driver code
int main()
{
    int N = 8;
 
    // Print function Call
    cout << print(N);
    return 0;
}

# Python3 program for the above approach
import bisect
 
# Function to find primes <= N
def SieveOfEratosthenes(n):
 
    # Create a boolean array
    # "prime[0..n]" and initialize
    # all entries it as true.
    # A value in prime[i] will
    # finally be false if i is
    # Not a prime, else true.
    prime = [True] * (n + 1)
     
    for p in range(2, 1 + int(n ** 0.5)):
         
        # If prime[p] is not changed,
        # then it is a prime
        if (prime[p] == True):
            # Update all multiples
            # of p greater than or
            # equal to the square of it
            for i in range(p * p, n + 1, p):
                prime[i] = False
 
    # Vector for storing prime number
    # less than or equal to N
    primes = []
 
    # Store all prime numbers
    for p in range(2, n + 1):
        if prime[p]:
            primes.append(p)
 
 
    return primes
 
 
# Find floor of cube root of N
def primeCubic(primes, N):
 
    #Val stores cube root of N
    l = 0
    r = N
 
    # Binary search loop for finding
    # floor of cube root of N
    while (l <= r):
        mid = (l + r) // 2
        if ((mid * mid * mid) <= N):
            val = mid
            l = mid + 1
         
        else:
            r = mid - 1
 
    # Iterator for finding index with
    # value just greater than Val in primes
    it = bisect.bisect_right(primes, val)
 
    return it
 
# Function to find primes with product <= N
def primeProduct(primes, N):
 
    # Stores the answer
    answer = 0
 
    # Iterator storing pointer to
    # current prime
    cur = 0
 
    # Loop for traversing all primes
    # Find number of indices less than
    # current indices for which product
    # is less than or equal to N
    for i in primes:
        add = bisect.bisect_right(primes[:cur], N // i)
        answer += add
        cur += 1
 
    return answer
 
# Function to find the total count
def print_(N):
 
    primes = SieveOfEratosthenes(N)
 
    answer = 0
    answer += primeCubic(primes, N)
    answer += primeProduct(primes, N)
    return answer
 
 
# Driver code
N = 8
 
# Print function Call
print(print_(N))
 
# This code is contributed by phasing17

2

Complejidad de tiempo: O(N * log(logN) + N + logN) ≈ O(N * log (logN))
Espacio auxiliar: O(N)