Dado un número N, la tarea es verificar si N puede representarse como el producto de un número primo y un número compuesto o no. Si puede, escriba Sí , de lo contrario , No.
Ejemplos:
Entrada: N = 52
Salida: Sí
Explicación: 52 se puede representar como la multiplicación de 4 y 13, donde 4 es un número compuesto y 13 es un número primo.Entrada: N = 49
Salida: No
Enfoque: Este problema se puede resolver con la ayuda del algoritmo Tamiz de Eratóstenes . Ahora, para resolver este problema, siga los siguientes pasos:
- Cree una array booleana isPrime , donde el i-ésimo elemento es verdadero si es primo, de lo contrario es falso .
- Encuentre todos los números primos hasta N usando el algoritmo de tamiz.
- Ahora ejecute un bucle para i=2 a i<N , y en cada iteración:
- Compruebe estas dos condiciones:
- Si N es divisible por i .
- Si i es un número primo y N/i no lo es o si i no es un número primo y N/i lo es.
- Si se cumplen las dos condiciones anteriores, devuelve true .
- De lo contrario, devuelve falso .
- Compruebe estas dos condiciones:
- Escriba la respuesta, de acuerdo con la observación anterior.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to generate all prime
// numbers less than N
void SieveOfEratosthenes(int N, bool isPrime[])
{
// Initialize all entries of boolean array
// as true. A value in isPrime[i] will finally
// be false if i is Not a prime, else true
// bool isPrime[N+1];
isPrime[0] = isPrime[1] = false;
for (int i = 2; i <= N; i++)
isPrime[i] = true;
for (int p = 2; p * p <= N; p++) {
// If isPrime[p] is not changed,
// then it is a prime
if (isPrime[p] == true) {
// Update all multiples of p
for (int i = p * 2; i <= N; i += p)
isPrime[i] = false;
}
}
}
// Function to check if we can
// represent N as product of a prime
// and a composite number or not
bool isRepresentable(int N)
{
// Generating primes using Sieve
bool isPrime[N + 1];
SieveOfEratosthenes(N, isPrime);
// Traversing through the array
for (int i = 2; i < N; i++) {
if (N % i == 0) {
if (N % i == 0
and (isPrime[i] and !isPrime[N / i])
or (!isPrime[i] and isPrime[N / i])) {
return true;
}
}
}
return false;
}
// Driver Code
int main()
{
int N = 52;
if (isRepresentable(N)) {
cout << "Yes";
}
else {
cout << "No";
}
return 0;
}
Java
// Java program to implement the above approach
import java.util.*;
public class GFG
{
// Function to generate all prime
// numbers less than N
static void SieveOfEratosthenes(int N, boolean []isPrime)
{
// Initialize all entries of boolean array
// as true. A value in isPrime[i] will finally
// be false if i is Not a prime, else true
// bool isPrime[N+1];
isPrime[0] = isPrime[1] = false;
for (int i = 2; i <= N; i++)
isPrime[i] = true;
for (int p = 2; p * p <= N; p++) {
// If isPrime[p] is not changed,
// then it is a prime
if (isPrime[p] == true) {
// Update all multiples of p
for (int i = p * 2; i <= N; i += p)
isPrime[i] = false;
}
}
}
// Function to check if we can
// represent N as product of a prime
// and a composite number or not
static boolean isRepresentable(int N)
{
// Generating primes using Sieve
boolean []isPrime = new boolean[N + 1];
SieveOfEratosthenes(N, isPrime);
// Traversing through the array
for (int i = 2; i < N; i++) {
if (N % i == 0) {
if (N % i == 0
&& (isPrime[i] && !isPrime[N / i])
|| (!isPrime[i] && isPrime[N / i])) {
return true;
}
}
}
return false;
}
// Driver Code
public static void main(String arg[])
{
int N = 52;
if (isRepresentable(N)) {
System.out.println("Yes");
}
else {
System.out.println("No");
}
}
}
// This code is contributed by Samim Hossain Mondal.
Python3
# python program for the above approach
import math
# Function to generate all prime
# numbers less than N
def SieveOfEratosthenes(N, isPrime):
# Initialize all entries of boolean array
# as true. A value in isPrime[i] will finally
# be false if i is Not a prime, else true
# bool isPrime[N+1];
isPrime[0] = False
isPrime[1] = False
for i in range(2, N+1):
isPrime[i] = True
for p in range(2, int(math.sqrt(N)) + 1):
# If isPrime[p] is not changed,
# then it is a prime
if (isPrime[p] == True):
# Update all multiples of p
for i in range(p+2, N+1, p):
isPrime[i] = False
# Function to check if we can
# represent N as product of a prime
# and a composite number or not
def isRepresentable(N):
# Generating primes using Sieve
isPrime = [0 for _ in range(N + 1)]
SieveOfEratosthenes(N, isPrime)
# Traversing through the array
for i in range(2, N):
if (N % i == 0):
if (N % i == 0 and (isPrime[i] and not isPrime[N // i]) or (not isPrime[i] and isPrime[N // i])):
return True
return False
# Driver Code
if __name__ == "__main__":
N = 52
if (isRepresentable(N)):
print("Yes")
else:
print("No")
# This code is contributed by rakeshsahni
C#
// C# program to implement the above approach
using System;
class GFG
{
// Function to generate all prime
// numbers less than N
static void SieveOfEratosthenes(int N, bool []isPrime)
{
// Initialize all entries of boolean array
// as true. A value in isPrime[i] will finally
// be false if i is Not a prime, else true
// bool isPrime[N+1];
isPrime[0] = isPrime[1] = false;
for (int i = 2; i <= N; i++)
isPrime[i] = true;
for (int p = 2; p * p <= N; p++) {
// If isPrime[p] is not changed,
// then it is a prime
if (isPrime[p] == true) {
// Update all multiples of p
for (int i = p * 2; i <= N; i += p)
isPrime[i] = false;
}
}
}
// Function to check if we can
// represent N as product of a prime
// and a composite number or not
static bool isRepresentable(int N)
{
// Generating primes using Sieve
bool []isPrime = new bool[N + 1];
SieveOfEratosthenes(N, isPrime);
// Traversing through the array
for (int i = 2; i < N; i++) {
if (N % i == 0) {
if (N % i == 0
&& (isPrime[i] && !isPrime[N / i])
|| (!isPrime[i] && isPrime[N / i])) {
return true;
}
}
}
return false;
}
// Driver Code
public static void Main()
{
int N = 52;
if (isRepresentable(N)) {
Console.Write("Yes");
}
else {
Console.Write("No");
}
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// Javascript program for the above approach
// Function to generate all prime
// numbers less than N
function SieveOfEratosthenes(N, isPrime)
{
// Initialize all entries of boolean array
// as true. A value in isPrime[i] will finally
// be false if i is Not a prime, else true
// bool isPrime[N+1];
isPrime[0] = isPrime[1] = false;
for (let i = 2; i <= N; i++)
isPrime[i] = true;
for (let p = 2; p * p <= N; p++) {
// If isPrime[p] is not changed,
// then it is a prime
if (isPrime[p] == true) {
// Update all multiples of p
for (let i = p * 2; i <= N; i += p)
isPrime[i] = false;
}
}
}
// Function to check if we can
// represent N as product of a prime
// and a composite number or not
function isRepresentable(N)
{
// Generating primes using Sieve
let isPrime = [];
SieveOfEratosthenes(N, isPrime);
// Traversing through the array
for (let i = 2; i < N; i++) {
if (N % i == 0) {
if (N % i == 0
&& (isPrime[i] && !isPrime[N / i])
|| (!isPrime[i] && isPrime[N / i])) {
return true;
}
}
}
return false;
}
// Driver Code
let N = 52;
if (isRepresentable(N)) {
document.write("Yes");
}
else {
document.write("No");
}
// This code is contributed by Samim Hossain Mondal.
</script>
Producción
Yes
Complejidad de tiempo: O(N*log(logN))
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por subhankarjadab y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA