Dados dos números enteros L y R , la tarea es calcular el conteo de números del rango [L, R] que tienen exactamente 5 factores positivos distintos.
Ejemplos:
Entrada: L = 1, R= 100
Salida: 2
Explicación: Los únicos dos números en el rango [1, 100] que tienen exactamente 5 factores primos son 16 y 81. Los
factores de 16 son {1, 2, 4, 8, 16 }.
Los factores de 8 son {1, 3, 9, 27, 81}.Entrada: L = 1, R= 100
Salida: 2
Enfoque ingenuo: el enfoque más simple para resolver este problema es atravesar el rango [L, R] y, para cada número, contar sus factores. Si el conteo de factores es igual a 5 , incremente el conteo en 1 .
Complejidad de tiempo: (R – L) × √N
Espacio auxiliar: O(1)
Enfoque eficiente: Para optimizar el enfoque anterior, es necesario hacer la siguiente observación con respecto a los números que tienen exactamente 5 factores.
Sea la descomposición en factores primos de un número p 1 a 1 ×p 2 a 2 × … ×p n a n .
Por lo tanto, la cuenta de factores de este número se puede escribir como (a 1 + 1)×(a 2 + 1)× … ×(a n + 1).
Como este producto debe ser igual a 5 (que es un número primo ), solo debe existir un término mayor que 1 en el producto. Ese término debe ser igual a 5.
Por lo tanto, si a i + 1 = 5
=> a i = 4
Siga los pasos a continuación para resolver el problema:
- El conteo requerido es el conteo de números en el rango que contiene p 4 como factor, donde p es un número primo.
- Para calcular eficientemente p 4 para un amplio rango ( [1, 10 18 ] ), la idea es usar la Criba de Eratóstenes para almacenar todos los números primos hasta 10 4.5 .
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5;
// Stores all prime numbers
// up to 2 * 10^5
vector<long long> prime;
// Function to generate all prime
// numbers up to 2 * 10 ^ 5 using
// Sieve of Eratosthenes
void Sieve()
{
prime.clear();
vector<bool> p(N + 1, true);
// Mark 0 and 1 as non-prime
p[0] = p[1] = false;
for (int i = 2; i * i <= N; i++) {
// If i is prime
if (p[i] == true) {
// Mark all its factors as non-prime
for (int j = i * i; j <= N; j += i) {
p[j] = false;
}
}
}
for (int i = 1; i < N; i++) {
// If current number is prime
if (p[i]) {
// Store the prime
prime.push_back(1LL * pow(i, 4));
}
}
}
// Function to count numbers in the
// range [L, R] having exactly 5 factors
void countNumbers(long long int L,
long long int R)
{
// Stores the required count
int Count = 0;
for (int p : prime) {
if (p >= L && p <= R) {
Count++;
}
}
cout << Count << endl;
}
// Driver Code
int main()
{
long long L = 16, R = 85000;
Sieve();
countNumbers(L, R);
return 0;
}
Java
// Java Program to implement
// the above approach
import java.util.*;
class GFG
{
static int N = 200000;
// Stores all prime numbers
// up to 2 * 10^5
static int prime[] = new int [20000];
static int index = 0;
// Function to generate all prime
// numbers up to 2 * 10 ^ 5 using
// Sieve of Eratosthenes
static void Sieve()
{
index = 0;
int p[] = new int [N + 1];
for(int i = 0; i <= N; i++)
{
p[i] = 1;
}
// Mark 0 and 1 as non-prime
p[0] = p[1] = 0;
for (int i = 2; i * i <= N; i++)
{
// If i is prime
if (p[i] == 1)
{
// Mark all its factors as non-prime
for (int j = i * i; j <= N; j += i)
{
p[j] = 0;
}
}
}
for (int i = 1; i < N; i++)
{
// If current number is prime
if (p[i] == 1)
{
// Store the prime
prime[index++] = (int)(Math.pow(i, 4));
}
}
}
// Function to count numbers in the
// range [L, R] having exactly 5 factors
static void countNumbers(int L,int R)
{
// Stores the required count
int Count = 0;
for(int i = 0; i < index; i++)
{
int p = prime[i];
if (p >= L && p <= R)
{
Count++;
}
}
System.out.println(Count);
}
// Driver Code
public static void main(String[] args)
{
int L = 16, R = 85000;
Sieve();
countNumbers(L, R);
}
}
// This code is contributed by amreshkumar3.
Python3
# Python3 implementation of # the above approach N = 2 * 100000 # Stores all prime numbers # up to 2 * 10^5 prime = [0] * N # Function to generate all prime # numbers up to 2 * 10 ^ 5 using # Sieve of Eratosthenes def Sieve() : p = [True] * (N + 1) # Mark 0 and 1 as non-prime p[0] = p[1] = False i = 2 while(i * i <= N) : # If i is prime if (p[i] == True) : # Mark all its factors as non-prime for j in range(i * i, N, i): p[j] = False i += 1 for i in range(N): # If current number is prime if (p[i] != False) : # Store the prime prime.append(pow(i, 4)) # Function to count numbers in the # range [L, R] having exactly 5 factors def countNumbers(L, R) : # Stores the required count Count = 0 for p in prime : if (p >= L and p <= R) : Count += 1 print(Count) # Driver Code L = 16 R = 85000 Sieve() countNumbers(L, R) # This code is contributed by code_hunt.
C#
// C# Program to implement
// the above approach
using System;
class GFG
{
static int N = 200000;
// Stores all prime numbers
// up to 2 * 10^5
static int []prime = new int [20000];
static int index = 0;
// Function to generate all prime
// numbers up to 2 * 10 ^ 5 using
// Sieve of Eratosthenes
static void Sieve()
{
index = 0;
int []p = new int [N + 1];
for(int i = 0; i <= N; i++)
{
p[i] = 1;
}
// Mark 0 and 1 as non-prime
p[0] = p[1] = 0;
for (int i = 2; i * i <= N; i++)
{
// If i is prime
if (p[i] == 1)
{
// Mark all its factors as non-prime
for (int j = i * i; j <= N; j += i)
{
p[j] = 0;
}
}
}
for (int i = 1; i < N; i++)
{
// If current number is prime
if (p[i] == 1)
{
// Store the prime
prime[index++] = (int)(Math.Pow(i, 4));
}
}
}
// Function to count numbers in the
// range [L, R] having exactly 5 factors
static void countNumbers(int L,int R)
{
// Stores the required count
int Count = 0;
for(int i = 0; i < index; i++)
{
int p = prime[i];
if (p >= L && p <= R)
{
Count++;
}
}
Console.WriteLine(Count);
}
// Driver Code
public static void Main(String[] args)
{
int L = 16, R = 85000;
Sieve();
countNumbers(L, R);
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// javascript program of the above approach
let N = 200000;
// Stores all prime numbers
// up to 2 * 10^5
let prime = new Array(20000).fill(0);
let index = 0;
// Function to generate all prime
// numbers up to 2 * 10 ^ 5 using
// Sieve of Eratosthenes
function Sieve()
{
index = 0;
let p = new Array (N + 1).fill(0);
for(let i = 0; i <= N; i++)
{
p[i] = 1;
}
// Mark 0 and 1 as non-prime
p[0] = p[1] = 0;
for (let i = 2; i * i <= N; i++)
{
// If i is prime
if (p[i] == 1)
{
// Mark all its factors as non-prime
for (let j = i * i; j <= N; j += i)
{
p[j] = 0;
}
}
}
for (let i = 1; i < N; i++)
{
// If current number is prime
if (p[i] == 1)
{
// Store the prime
prime[index++] = (Math.pow(i, 4));
}
}
}
// Function to count numbers in the
// range [L, R] having exactly 5 factors
function countNumbers(L, R)
{
// Stores the required count
let Count = 0;
for(let i = 0; i < index; i++)
{
let p = prime[i];
if (p >= L && p <= R)
{
Count++;
}
}
document.write(Count);
}
// Driver Code
let L = 16, R = 85000;
Sieve();
countNumbers(L, R);
</script>
7
Complejidad de tiempo: O(N * log(log(N)) )
Espacio auxiliar: O(N)