Dado un entero positivo N , la tarea es contar el número de enteros del rango [1, N] que tienen exactamente 5 divisores .
Ejemplos:
Entrada: N = 18
Salida: 1
Explicación:
De todos los enteros sobre el rango [1, 18], 16 es el único entero que tiene exactamente 5 divisores, es decir, 1, 2, 8, 4 y 16.
Por lo tanto, la cuenta de tales enteros es 1.Entrada: N = 100
Salida: 2
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es iterar sobre el rango [1, N] y contar los enteros en este rango que tienen el recuento de divisores como 5 .
Complejidad de Tiempo: O(N 4/3 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior también se puede optimizar observando el hecho de que los números que tienen exactamente 5 divisores se pueden expresar en la forma de p 4 , donde p es un número primo ya que el recuento de divisores es exactamente 5 . Siga los pasos a continuación para resolver el problema:
- Genere todos los números primos de modo que su cuarta potencia sea menor que 10 18 usando la criba de Eratóstenes y almacénelos en un vector , digamos A[] .
- Inicialice dos variables, digamos bajo como 0 y alto como A.size() – 1 .
- Para realizar la iteración de búsqueda binaria hasta que el nivel bajo sea menor que el nivel alto y realice los siguientes pasos:
- Encuentre el valor de mid como (low + high)/2 .
- Encuentre el valor de la cuarta potencia del elemento en los índices mid (mid – 1) y guárdelo en una variable, digamos actual y anterior , respectivamente.
- Si el valor de la corriente es N , imprima el valor de A[mid] como resultado.
- Si el valor de la corriente es mayor que N y el anterior es como máximo N , imprima el valor de A[mid] como resultado.
- Si el valor de la corriente es mayor que N , actualice el valor de alto como (mid – 1) . De lo contrario, actualice el valor de low como (mid + 1) .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
#define ll long long int
const int MAX = 1e5;
using namespace std;
// Function to calculate the value of
// (x^y) using binary exponentiation
ll power(ll x, unsigned ll y)
{
// Stores the value of x^y
ll res = 1;
// Base Case
if (x == 0)
return 0;
while (y > 0) {
// If y is odd multiply
// x with result
if (y & 1)
res = (res * x);
// Otherwise, divide y by 2
y = y >> 1;
x = (x * x);
}
return res;
}
// Function to perform the Sieve Of
// Eratosthenes to find the prime
// number over the range [1, 10^5]
void SieveOfEratosthenes(
vector<pair<ll, ll> >& v)
{
bool prime[MAX + 1];
memset(prime, true, sizeof(prime));
prime[1] = false;
for (int p = 2; p * p <= MAX; p++) {
// If prime[p] is not changed
// then it is a prime
if (prime[p] == true) {
// Set all the multiples of
// p to non-prime
for (int i = p * 2;
i <= MAX; i += p)
prime[i] = false;
}
}
int num = 1;
// Iterate over the range [1, MAX]
for (int i = 1; i <= MAX; i++) {
// Store all the prime number
if (prime[i]) {
v.push_back({ i, num });
num++;
}
}
}
// Function to find the primes having
// only 5 divisors
int countIntegers(ll n)
{
// Base Case
if (n < 16) {
return 0;
}
// First value of the pair has the
// prime number and the second value
// has the count of primes till that
// prime numbers
vector<pair<ll, ll> > v;
// Precomputing all the primes
SieveOfEratosthenes(v);
int low = 0;
int high = v.size() - 1;
// Perform the Binary search
while (low <= high) {
int mid = (low + high) / 2;
// Calculate the fourth power of
// the curr and prev
ll curr = power(v[mid].first, 4);
ll prev = power(v[mid - 1].first, 4);
if (curr == n) {
// Return value of mid
return v[mid].second;
}
else if (curr > n and prev <= n) {
// Return value of mid-1
return v[mid - 1].second;
}
else if (curr > n) {
// Update the value of high
high = mid - 1;
}
else {
// Update the value of low
low = mid + 1;
}
}
return 0;
}
// Driver Code
int main()
{
ll N = 100;
cout << countIntegers(N);
return 0;
}
Java
// Java program for the above approach
import java.util.Vector;
public class GFG {
static int MAX = (int)1e5;
public static class pair {
long first;
long second;
pair(long first, long second)
{
this.first = first;
this.second = second;
}
}
// Function to calculate the value of
// (x^y) using binary exponentiation
static long power(long x, long y)
{
// Stores the value of x^y
long res = 1;
// Base Case
if (x == 0)
return 0;
while (y > 0)
{
// If y is odd multiply
// x with result
if ((y & 1) == 1)
res = (res * x);
// Otherwise, divide y by 2
y = y >> 1;
x = (x * x);
}
return res;
}
// Function to perform the Sieve Of
// Eratosthenes to find the prime
// number over the range [1, 10^5]
static void SieveOfEratosthenes(Vector<pair> v)
{
boolean prime[] = new boolean[MAX + 1];
for (int i = 0; i < prime.length; i++) {
prime[i] = true;
}
prime[1] = false;
for (int p = 2; p * p <= MAX; p++) {
// If prime[p] is not changed
// then it is a prime
if (prime[p] == true) {
// Set all the multiples of
// p to non-prime
for (int i = p * 2; i <= MAX; i += p)
prime[i] = false;
}
}
int num = 1;
// Iterate over the range [1, MAX]
for (int i = 1; i <= MAX; i++) {
// Store all the prime number
if (prime[i]) {
v.add(new pair(i, num));
num++;
}
}
}
// Function to find the primes having
// only 5 divisors
static long countIntegers(long n)
{
// Base Case
if (n < 16) {
return 0;
}
// First value of the pair has the
// prime number and the second value
// has the count of primes till that
// prime numbers
Vector<pair> v = new Vector<>();
// Precomputing all the primes
SieveOfEratosthenes(v);
int low = 0;
int high = v.size() - 1;
// Perform the Binary search
while (low <= high) {
int mid = (low + high) / 2;
// Calculate the fourth power of
// the curr and prev
long curr = power(v.get(mid).first, 4);
long prev = power(v.get(mid - 1).first, 4);
if (curr == n) {
// Return value of mid
return v.get(mid).second;
}
else if (curr > n && prev <= n) {
// Return value of mid-1
return v.get(mid - 1).second;
}
else if (curr > n) {
// Update the value of high
high = mid - 1;
}
else {
// Update the value of low
low = mid + 1;
}
}
return 0;
}
// Driver code
public static void main(String[] args)
{
long N = 100;
System.out.println(countIntegers(N));
}
}
// This code is contributed by abhinavjain194
Producción:
2
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por sapu10lm39 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA