Dado un entero positivo N , la tarea es encontrar todos los tripletes primos {P, Q, R} tales que P = R – Q y P , Q y R sean menores que N .
Ejemplos:
Entrada: N = 8
Salida:
2 3 5
2 5 7
Explicación:
Los únicos 2 tripletes primos que satisfacen las condiciones dadas son:
- {2, 3, 5}: P = 2, Q = 3, R = 5. Por lo tanto, P, Q y R son números primos y P = R – Q.
- {2, 5, 7}: P = 2, Q = 5, R = 7. Por lo tanto, P, Q y R son números primos y P = R – Q.
Entrada: N = 5
Salida: 2 3 5
Enfoque: El problema dado se puede resolver con base en las siguientes observaciones:
- Al reorganizar la ecuación dada, se puede observar que P + Q = R , y la suma de dos números impares es par y la suma de uno impar y uno par es impar .
- Como solo hay un primo par, es decir, 2 . Si P es un primo impar y Q es un primo impar, entonces R nunca puede ser un número primo, por lo que es necesario que P siempre sea 2 , que es un primo par y Q es un primo impar , entonces R debe ser un número primo impar . Por lo tanto, es necesario encontrar el primo Q tal que Q > 2 y R = P + Q ≤ N (donde P = 2) y R debe ser primo .
Siga los pasos a continuación para resolver el problema:
- Calcule previamente todos los números primos en el rango [1, N] usando la criba de Eratóstenes .
- Inicialice un vector de vectores , digamos V , para almacenar todos los tripletes resultantes.
- Iterar sobre el rango [3, N] usando una variable, digamos i . Si i y (i + 2) son primos y 2 + i ≤ N , almacene los tripletes actuales en el vector V .
- Después de completar los pasos anteriores, imprima todos los tripletes almacenados en V[] .
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;
// Stores 1 and 0 at indices which
// are prime and non-prime respectively
bool prime[100000];
// Function to find all prime
// numbers from the range [0, N]
void SieveOfEratosthenes(int n)
{
// Consider all numbers to prime initially
memset(prime, true, sizeof(prime));
// Iterate over the range [2, sqrt(N)]
for (int p = 2; p * p <= n; p++) {
// If p is a prime
if (prime[p] == true) {
// Update all tultiples
// of p as false
for (int i = p * p;
i <= n; i += p) {
prime[i] = false;
}
}
}
}
// Function to find all prime triplets
// satisfying the given conditions
void findTriplets(int N)
{
// Generate all primes up to N
SieveOfEratosthenes(N);
// Stores the triplets
vector<vector<int> > V;
// Iterate over the range [3, N]
for (int i = 3; i <= N; i++) {
// Check for the condition
if (2 + i <= N && prime[i]
&& prime[2 + i]) {
// Store the triplets
V.push_back({ 2, i, i + 2 });
}
}
// Print all the stored triplets
for (int i = 0; i < V.size(); i++) {
cout << V[i][0] << " "
<< V[i][1] << " "
<< V[i][2] << "\n";
}
}
// Driver Code
int main()
{
int N = 8;
findTriplets(N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Stores 1 and 0 at indices which
// are prime and non-prime respectively
static boolean[] prime = new boolean[100000];
static void initialize()
{
for(int i = 0; i < 100000; i++)
prime[i] = true;
}
// Function to find all prime
// numbers from the range [0, N]
static void SieveOfEratosthenes(int n)
{
// Iterate over the range [2, sqrt(N)]
for(int p = 2; p * p <= n; p++)
{
// If p is a prime
if (prime[p] == true)
{
// Update all tultiples
// of p as false
for(int i = p * p; i <= n; i += p)
{
prime[i] = false;
}
}
}
}
// Function to find all prime triplets
// satisfying the given conditions
static void findTriplets(int N)
{
// Generate all primes up to N
SieveOfEratosthenes(N);
// Stores the triplets
ArrayList<ArrayList<Integer>> V = new ArrayList<ArrayList<Integer>>();
// List<List<int> > V = new List<List<int>>();
// Iterate over the range [3, N]
for(int i = 3; i <= N; i++)
{
// Check for the condition
if (2 + i <= N && prime[i] && prime[2 + i])
{
// Store the triplets
ArrayList<Integer> a1 = new ArrayList<Integer>();
a1.add(2);
a1.add(i);
a1.add(i + 2);
V.add(a1);
}
}
// Print all the stored triplets
for(int i = 0; i < V.size(); i++)
{
System.out.println(V.get(i).get(0) + " " +
V.get(i).get(1) + " " +
V.get(i).get(2));
}
}
// Driver Code
public static void main(String args[])
{
initialize();
int N = 8;
findTriplets(N);
}
}
// This code is contributed by ipg2016107
Python3
# Python3 program for the above approach from math import sqrt # Stores 1 and 0 at indices which # are prime and non-prime respectively prime = [True for i in range(100000)] # Function to find all prime # numbers from the range [0, N] def SieveOfEratosthenes(n): # Iterate over the range [2, sqrt(N)] for p in range(2, int(sqrt(n)) + 1, 1): # If p is a prime if (prime[p] == True): # Update all tultiples # of p as false for i in range(p * p, n + 1, p): prime[i] = False # Function to find all prime triplets # satisfying the given conditions def findTriplets(N): # Generate all primes up to N SieveOfEratosthenes(N) # Stores the triplets V = [] # Iterate over the range [3, N] for i in range(3, N + 1, 1): # Check for the condition if (2 + i <= N and prime[i] and prime[2 + i]): # Store the triplets V.append([2, i, i + 2]) # Print all the stored triplets for i in range(len(V)): print(V[i][0], V[i][1], V[i][2]) # Driver Code if __name__ == '__main__': N = 8 findTriplets(N) # This code is contributed by bgangwar59.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Stores 1 and 0 at indices which
// are prime and non-prime respectively
static bool[] prime = new bool[100000];
static void initialize()
{
for(int i = 0; i < 100000; i++)
prime[i] = true;
}
// Function to find all prime
// numbers from the range [0, N]
static void SieveOfEratosthenes(int n)
{
// Iterate over the range [2, sqrt(N)]
for(int p = 2; p * p <= n; p++)
{
// If p is a prime
if (prime[p] == true)
{
// Update all tultiples
// of p as false
for(int i = p * p; i <= n; i += p)
{
prime[i] = false;
}
}
}
}
// Function to find all prime triplets
// satisfying the given conditions
static void findTriplets(int N)
{
// Generate all primes up to N
SieveOfEratosthenes(N);
// Stores the triplets
List<List<int>> V = new List<List<int>>();
// Iterate over the range [3, N]
for(int i = 3; i <= N; i++)
{
// Check for the condition
if (2 + i <= N && prime[i] ==
true && prime[2 + i])
{
// Store the triplets
List<int> a1 = new List<int>();
a1.Add(2);
a1.Add(i);
a1.Add(i + 2);
V.Add(a1);
}
}
// Print all the stored triplets
for(int i = 0; i < V.Count; i++)
{
Console.WriteLine(V[i][0] + " " +
V[i][1] + " " +
V[i][2]);
}
}
// Driver Code
public static void Main()
{
initialize();
int N = 8;
findTriplets(N);
}
}
// This code is contributed by SURENDRA_GANGWAR
Javascript
<script>
// Javascript program for the above approach
// Stores 1 and 0 at indices which
// are prime and non-prime respectively
var prime = new Array(100000);
// Function to find all prime
// numbers from the range [0, N]
function SieveOfEratosthenes(n)
{
// Consider all numbers to prime initially
prime.fill(true);
// Iterate over the range [2, sqrt(N)]
for(var p = 2; p * p <= n; p++)
{
// If p is a prime
if (prime[p] == true)
{
// Update all tultiples
// of p as false
for(var i = p * p;
i <= n; i += p)
{
prime[i] = false;
}
}
}
}
// Function to find all prime triplets
// satisfying the given conditions
function findTriplets(N)
{
// Generate all primes up to N
SieveOfEratosthenes(N);
// Stores the triplets
var V = [];
// Iterate over the range [3, N]
for(var i = 3; i <= N; i++)
{
// Check for the condition
if (2 + i <= N && prime[i] == true &&
prime[2 + i] == true)
{
// Store the triplets
var a1 = [2, i, i + 2];
V.push(a1);
}
}
// Print all the stored triplets
for(var i = 0; i < V.length; i++)
{
document.write(V[i][0] + " " +
V[i][1] + " " +
V[i][2] + "<br>");
}
}
// Driver code
N = 8;
findTriplets(N);
// This code is contributed by SoumikMondal
</script>
Producción:
2 3 5 2 5 7
Complejidad de tiempo: O(N*log(log(N)))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por kapil16garg y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA