Dados los números enteros positivos ‘q’ y ‘n’. Para cada consulta ‘q’ encuentre si un número ‘n’ tiene exactamente cuatro divisores distintos o no. Si el número tiene exactamente cuatro divisores, imprima ‘Sí’, de lo contrario, ‘No’.1 <= q, n <= 10 6
Input: 2 10 12 Output: Yes No Explanation: For 1st query, n = 10 has exactly four divisor i.e., 1, 2, 5, 10. For 2nd query, n = 12 has exactly six divisor i.e., 1, 2, 3, 4, 6, 12.
El enfoque simple es contar factores generando todos los divisores de un número usando este enfoque, luego verifique si el conteo de todos los factores es igual a ‘4’ o no. La complejidad temporal de este enfoque es O(sqrt(n)).
Un mejor enfoque es utilizar la teoría de números . Para que un número tenga cuatro divisores debe cumplir las siguientes condiciones:
- Si el número es un producto de exactamente dos números primos (digamos p, q). Así podemos asegurar que tendrá cuatro factores, es decir, 1, p, q, n.
- Si un número es el cubo de un número primo (o la raíz cúbica del número es primo). Por ejemplo, digamos n = 8, raíz cúbica = 2, lo que significa que ‘8’ se puede escribir como 2*2*2, por lo que los cuatro factores son: 1, 2, 4 y 8.
Podemos usar la criba de Eratóstenes de modo que precalcularemos todos los factores primos del 1 al 10 6 . Ahora marcaremos todos los números que son el producto de dos números primos usando dos ‘bucles for’, es decir, marcar [p * q] = verdadero. Mientras tanto, también marcaremos todos los números (raíz cúbica) tomando el cubo del número, es decir, marcar [p * p * p] = verdadero.
Después de eso, podemos responder fácilmente cada consulta en tiempo O (1).
A continuación se muestra el pseudocódigo, eche un vistazo para una mejor comprensión
C++
// C++ program to check whether number has
// exactly four distinct factors or not
#include <bits/stdc++.h>
using namespace std;
// Initialize global variable according
// to given condition so that it can be
// accessible to all function
const int N = 1e6;
bool fourDiv[N + 1];
// Function to calculate all number having
// four distinct distinct factors
void fourDistinctFactors()
{
// 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 primeAll[N + 1];
memset(primeAll, true, sizeof(primeAll));
for (int p = 2; p * p <= N; p++) {
// If prime[p] is not changed, then it
// is a prime
if (primeAll[p] == true) {
// Update all multiples of p
for (int i = p * 2; i <= N; i += p)
primeAll[i] = false;
}
}
// Initialize prime[] array which will
// contains all the primes from 1-N
vector<int> prime;
for (int p = 2; p <= N; p++)
if (primeAll[p])
prime.push_back(p);
// Set the marking of all primes to false
memset(fourDiv, false, sizeof(fourDiv));
// Iterate over all the prime numbers
for (int i = 0; i < prime.size(); ++i) {
int p = prime[i];
// Mark cube root of prime numbers
if (1LL * p * p * p <= N)
fourDiv[p * p * p] = true;
for (int j = i + 1; j < prime.size(); ++j) {
int q = prime[j];
if (1LL * p * q > N)
break;
// Mark product of prime numbers
fourDiv[p * q] = true;
}
}
}
// Driver program
int main()
{
fourDistinctFactors();
int num = 10;
if (fourDiv[num])
cout << "Yes\n";
else
cout << "No\n";
num = 12;
if (fourDiv[num])
cout << "Yes\n";
else
cout << "No\n";
return 0;
}
Java
// Java program to check whether number has
// exactly four distinct factors or not
import java.util.*;
class GFG{
// Initialize global variable according
// to given condition so that it can be
// accessible to all function
static int N = (int)1E6;
static boolean[] fourDiv=new boolean[N + 1];
// Function to calculate all number having
// four distinct distinct factors
static void fourDistinctFactors()
{
// 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.
boolean[] primeAll=new boolean[N + 1];
for (int p = 2; p * p <= N; p++) {
// If prime[p] is not changed, then it
// is a prime
if (primeAll[p] == false) {
// Update all multiples of p
for (int i = p * 2; i <= N; i += p)
primeAll[i] = true;
}
}
// Initialize prime[] array which will
// contains all the primes from 1-N
ArrayList<Integer> prime=new ArrayList<Integer>();
for (int p = 2; p <= N; p++)
if (!primeAll[p])
prime.add(p);
// Iterate over all the prime numbers
for (int i = 0; i < prime.size(); ++i) {
int p = prime.get(i);
// Mark cube root of prime numbers
if (1L * p * p * p <= N)
fourDiv[p * p * p] = true;
for (int j = i + 1; j < prime.size(); ++j) {
int q = prime.get(j);
if (1L * p * q > N)
break;
// Mark product of prime numbers
fourDiv[p * q] = true;
}
}
}
// Driver program
public static void main(String[] args)
{
fourDistinctFactors();
int num = 10;
if (fourDiv[num])
System.out.println("Yes");
else
System.out.println("No");
num = 12;
if (fourDiv[num])
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by mits
Python3
# Python3 program to check whether number
# has exactly four distinct factors or not
# Initialize global variable according to
# given condition so that it can be
# accessible to all function
N = 1000001;
fourDiv = [False] * (N + 1);
# Function to calculate all number
# having four distinct factors
def fourDistinctFactors():
# 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.
primeAll = [True] * (N + 1);
p = 2;
while (p * p <= N):
# If prime[p] is not changed, then it
# is a prime
if (primeAll[p] == True):
# Update all multiples of p
i = p * 2;
while (i <= N):
primeAll[i] = False;
i += p;
p += 1;
# Initialize prime[] array which will
# contain all the primes from 1-N
prime = [];
for p in range(2, N + 1):
if (primeAll[p]):
prime.append(p);
# Iterate over all the prime numbers
for i in range(len(prime)):
p = prime[i];
# Mark cube root of prime numbers
if (1 * p * p * p <= N):
fourDiv[p * p * p] = True;
for j in range(i + 1, len(prime)):
q = prime[j];
if (1 * p * q > N):
break;
# Mark product of prime numbers
fourDiv[p * q] = True;
# Driver Code
fourDistinctFactors();
num = 10;
if (fourDiv[num]):
print("Yes");
else:
print("No");
num = 12;
if (fourDiv[num]):
print("Yes");
else:
print("No");
# This code is contributed by mits
C#
// C# program to check whether number has
// exactly four distinct factors or not
using System;
using System.Collections;
class GFG
{
// Initialize global variable according
// to given condition so that it can be
// accessible to all function
static int N = (int)1E6;
static bool[] fourDiv = new bool[N + 1];
// Function to calculate all number having
// four distinct distinct factors
static void fourDistinctFactors()
{
// 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[] primeAll = new bool[N + 1];
for (int p = 2; p * p <= N; p++)
{
// If prime[p] is not changed,
// then it is a prime
if (primeAll[p] == false)
{
// Update all multiples of p
for (int i = p * 2; i <= N; i += p)
primeAll[i] = true;
}
}
// Initialize prime[] array which will
// contains all the primes from 1-N
ArrayList prime = new ArrayList();
for (int p = 2; p <= N; p++)
if (!primeAll[p])
prime.Add(p);
// Iterate over all the prime numbers
for (int i = 0; i < prime.Count; ++i)
{
int p = (int)prime[i];
// Mark cube root of prime numbers
if (1L * p * p * p <= N)
fourDiv[p * p * p] = true;
for (int j = i + 1; j < prime.Count; ++j)
{
int q = (int)prime[j];
if (1L * p * q > N)
break;
// Mark product of prime numbers
fourDiv[p * q] = true;
}
}
}
// Driver Code
public static void Main()
{
fourDistinctFactors();
int num = 10;
if (fourDiv[num])
Console.WriteLine("Yes");
else
Console.WriteLine("No");
num = 12;
if (fourDiv[num])
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// This code is contributed by mits
PHP
<?php
// GFG PHP Compiler not support 64-bit
// PHP program to check whether
// number has exactly four
// distinct factors or not
// Initialize global variable
// according to given condition
// so that it can be accessible
// to all function
$N = 1000001;
$fourDiv = array_fill(0,
$N + 1, false);
// Function to calculate
// all number having four
// distinct factors
function fourDistinctFactors()
{
global $N;
global $fourDiv;
// 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.
$primeAll = array_fill(0, $N + 1, true);
for ($p = 2;
$p * $p <= $N; $p++)
{
// If prime[p] is not
// changed, then it
// is a prime
if ($primeAll[$p] == true)
{
// Update all multiples of p
for ($i = $p * 2;
$i <= $N; $i += $p)
$primeAll[$i] = false;
}
}
// Initialize prime[] array
// which will contains all
// the primes from 1-N
$prime;
$x = 0;
for ($p = 2; $p <= $N; $p++)
if ($primeAll[$p])
$prime[$x++] = $p;
// Iterate over all
// the prime numbers
for ($i = 0; $i < $x; ++$i)
{
$p = $prime[$i];
// Mark cube root
// of prime numbers
if (1 * $p * $p * $p <= $N)
$fourDiv[$p * $p * $p] = true;
for ($j = $i + 1;
$j < $x; ++$j)
{
$q = $prime[$j];
if (1 * $p * $q > $N)
break;
// Mark product of
// prime numbers
$fourDiv[$p * $q] = true;
}
}
}
// Driver Code
fourDistinctFactors();
$num = 10;
if ($fourDiv[$num])
echo "Yes\n";
else
echo "No\n";
$num = 12;
if ($fourDiv[$num])
echo "Yes\n";
else
echo "No\n";
// This code is contributed by mits
?>
Javascript
<script>
// JavaScript program to check whether number has
// exactly four distinct factors or not
// Initialize global variable according
// to given condition so that it can be
// accessible to all function
var N = 1000000;
var fourDiv = Array(N+1).fill(false);
// Function to calculate all number having
// four distinct distinct factors
function fourDistinctFactors()
{
// 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.
var primeAll = Array(N+1).fill(false);
for (var p = 2; p * p <= N; p++)
{
// If prime[p] is not changed,
// then it is a prime
if (primeAll[p] == false)
{
// Update all multiples of p
for (var i = p * 2; i <= N; i += p)
primeAll[i] = true;
}
}
// Initialize prime[] array which will
// contains all the primes from 1-N
var prime = [];
for (var p = 2; p <= N; p++)
if (!primeAll[p])
prime.push(p);
// Iterate over all the prime numbers
for (var i = 0; i < prime.length; ++i)
{
var p = prime[i];
// Mark cube root of prime numbers
if (p * p * p <= N)
fourDiv[p * p * p] = true;
for(var j = i + 1; j < prime.length; ++j)
{
var q = prime[j];
if (p * q > N)
break;
// Mark product of prime numbers
fourDiv[p * q] = true;
}
}
}
// Driver Code
fourDistinctFactors();
var num = 10;
if (fourDiv[num])
document.write("Yes<br>");
else
document.write("No<br>");
num = 12;
if (fourDiv[num])
document.write("Yes");
else
document.write("No");
</script>
Producción:
Yes No
Complejidad de tiempo: O(n log(log n))
Espacio auxiliar: O(n)
Este artículo es una contribución de Aarti_Rathi y Shubham Bansal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA