Dado un número N (mayor que 2). La tarea es encontrar dos números primos distintos cuyo producto sea igual al número dado. Puede haber varias combinaciones posibles. Imprima solo el primer par.
Si no es posible expresar N como producto de dos primos distintos, imprima «No es posible».
Ejemplos :
Input : N = 15 Output : 3, 5 3 and 5 are both primes and, 3*5 = 15 Input : N = 39 Output : 3, 13 3 and 13 are both primes and, 3*13 = 39
La idea es encontrar todos los primos menores o iguales al número dado N usando la Criba de Eratóstenes. Una vez que tenemos una array que dice todos los números primos, podemos atravesar esta array para encontrar un par con un producto dado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find a distinct prime number
// pair whose product is equal to given number
#include <bits/stdc++.h>
using namespace std;
// Function to generate all prime
// numbers less than n
bool 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 print a prime pair
// with given product
void findPrimePair(int n)
{
int flag = 0;
// Generating primes using Sieve
bool isPrime[n + 1];
SieveOfEratosthenes(n, isPrime);
// Traversing all numbers to find first
// pair
for (int i = 2; i < n; i++) {
int x = n / i;
if (isPrime[i] && isPrime[x] and x != i
and x * i == n) {
cout << i << " " << x;
flag = 1;
return;
}
}
if (!flag)
cout << "No such pair found";
}
// Driven Code
int main()
{
int n = 39;
findPrimePair(n);
return 0;
}
C
// C program to find a distinct prime number
// pair whose product is equal to given number
#include <stdio.h>
#include <stdbool.h>
// Function to generate all prime
// numbers less than n
bool 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 print a prime pair
// with given product
void findPrimePair(int n)
{
int flag = 0;
// Generating primes using Sieve
bool isPrime[n + 1];
SieveOfEratosthenes(n, isPrime);
// Traversing all numbers to find first
// pair
for (int i = 2; i < n; i++) {
int x = n / i;
if (isPrime[i] && isPrime[x] && x != i && x * i == n) {
printf("%d %d",i,x);
flag = 1;
return;
}
}
if (!flag)
printf("No such pair found");
}
// Driven Code
int main()
{
int n = 39;
findPrimePair(n);
return 0;
}
// This code is contributed by kothavvsaakash.
Java
// Java program to find a distinct prime number
// pair whose product is equal to given number
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 print a prime pair
// with given product
static void findPrimePair(int n)
{
int flag = 0;
// Generating primes using Sieve
boolean[] isPrime = new boolean[n + 1];
SieveOfEratosthenes(n, isPrime);
// Traversing all numbers to find first
// pair
for (int i = 2; i < n; i++) {
int x = n / i;
if (isPrime[i] && isPrime[x] && x != i
&& x * i == n) {
System.out.println(i + " " + x);
flag = 1;
return;
}
}
if (flag == 0)
System.out.println("No such pair found");
}
// Driven Code
public static void main(String[] args)
{
int n = 39;
findPrimePair(n);
}
}
// This code is contributed by
// ihritik
Python3
# Python3 program to find a distinct
# prime number pair whose product
# is equal to given number
# from math lib. import everything
from math import *
# 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], isPrime[1] = False, False
for i in range(2, n + 1) :
isPrime[i] = True
for p in range(2, int(sqrt(n)) + 1) :
# If isPrime[p] is not changed,
# then it is a prime
if isPrime[p] == True :
for i in range(p * 2, n + 1, p) :
isPrime[i] = False
# Function to print a prime pair
# with given product
def findPrimePair(n) :
flag = 0
# Generating primes using Sieve
isPrime = [False] * (n + 1)
SieveOfEratosthenes(n, isPrime)
# Traversing all numbers to
# find first pair
for i in range(2, n) :
x = int(n / i)
if (isPrime[i] & isPrime[x] and
x != i and x * i == n) :
print(i, x)
flag = 1
break
if not flag :
print("No such pair found")
# Driver code
if __name__ == "__main__" :
# Function calling
n = 39;
findPrimePair(n)
# This code is contributed by ANKITRAI1
C#
// C# program to find a distinct prime number
// pair whose product is equal to given number
using System;
class GFG
{
// Function to generate all
// prime numbers less than n
static void SieveOfEratosthenes(int n,
bool[] isPrime)
{
// Initialize all entries of bool
// 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 print a prime
// pair with given product
static void findPrimePair(int n)
{
int flag = 0;
// Generating primes using Sieve
bool[] isPrime = new bool[n + 1];
SieveOfEratosthenes(n, isPrime);
// Traversing all numbers to
// find first pair
for (int i = 2; i < n; i++)
{
int x = n / i;
if (isPrime[i] && isPrime[x] &&
x != i && x * i == n)
{
Console.Write(i + " " + x);
flag = 1;
return;
}
}
if (flag == 0)
Console.Write("No such pair found");
}
// Driven Code
public static void Main()
{
int n = 39;
findPrimePair(n);
}
}
// This code is contributed by ChitraNayal
PHP
<?php
// PHP program to find a distinct prime number
// pair whose product is equal to given number
// 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] = false;
$isPrime[1] = false;
for ($i = 2; $i <= $n; $i++)
$isPrime[$i] = true;
for ($p = 2; $p * $p <= $n; $p++)
{
// If isPrime[p] is not changed,
// then it is a prime
if ($isPrime[$p])
{
// Update all multiples of p
for ($i = $p * 2;
$i <= $n; $i += $p)
$isPrime[$i] = false;
}
}
}
// Function to print a prime pair
// with given product
function findPrimePair($n)
{
$flag = 0;
// Generating primes using Sieve
$isPrime = array_fill(0, ($n + 1), false);
SieveOfEratosthenes($n, $isPrime);
// Traversing all numbers to
// find first pair
for ($i = 2; $i < $n; $i++)
{
$x = (int)($n / $i);
if ($isPrime[$i] && $isPrime[$x] and
$x != $i and $x * $i == $n)
{
echo $i . " " . $x;
$flag = 1;
return;
}
}
if (!$flag)
echo "No such pair found";
}
// Driver Code
$n = 39;
findPrimePair($n);
// This code is contributed by mits
?>
Javascript
<script>
// Javascript program to find a distinct prime number
// pair whose product is equal to given number
// Function to generate all
// prime numbers less than n
function SieveOfEratosthenes(n, isPrime)
{
// Initialize all entries of bool
// array as true. A value in
// isPrime[i] will finally be false
// if i is Not a prime, else true
// isPrime[n+1];
isPrime[0] = isPrime[1] = false;
for(var i = 2; i <= n; i++)
isPrime[i] = true;
for(var 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(var i = p * 2; i <= n; i += p)
isPrime[i] = false;
}
}
}
// Function to print a prime
// pair with given product
function findPrimePair(n)
{
var flag = 0;
// Generating primes using Sieve
var isPrime = []
SieveOfEratosthenes(n, isPrime);
// Traversing all numbers to
// find first pair
for(var i = 2; i < n; i++)
{
var x = n / i;
if (isPrime[i] && isPrime[x] &&
x != i && x * i == n)
{
document.write(i + " " + x);
flag = 1;
return;
}
}
if (flag == 0)
document.write("No such pair found");
}
// Driver code
var n = 39;
findPrimePair(n);
// This code is contributed by bunnyram19
</script>
Producción:
3 13
Complejidad de tiempo: O(N*log log(N))
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA