Dado un entero positivo N , la tarea es encontrar el número de pares desordenados de números semiprimos en el rango [1, N] tales que su suma sea primo .
Ejemplos:
Entrada: N = 25
Salida: 5
Explicación:
Los pares válidos de números semiprimos cuya suma también es prima son (10, 21), (14, 15), (15, 22), (20, 21) y ( 21, 22). La cuenta de tales números es 5.Entrada: N = 100
Salida: 313
Planteamiento: El problema dado se puede resolver utilizando la Tamiz de Eratóstenes . Se puede crear una array prime[] donde prime[i] almacena los distintos factores primos del número utilizando el tamiz. Todos los números en el rango [1, N] con 2 factores primos distintos se pueden almacenar en un vector semiprimos . A partir de entonces, iterar sobre todos los pares no ordenados de semiprimos vectoriales y mantener el recuento de pares con la suma de los primos .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100000;
// Stores the count of distinct prime
// number in factor of current number
int prime[maxn] = {};
// Function to return the vector of
// semi prime numbers in range [1, N]
vector<int> semiPrimes(int N)
{
// Count of distinct prime number
// in the factor of current number
// using Sieve of Eratosthenes
for (int p = 2; p <= maxn; p++) {
// If current number is prime
if (prime[p] == 0) {
for (int i = 2 * p; i <= maxn; i += p)
prime[i]++;
}
}
// Stores the semi prime numbers
vector<int> sPrimes;
for (int p = 2; p <= N; p++)
// If p has 2 distinct prime factors
if (prime[p] == 2)
sPrimes.push_back(p);
// Return vector
return sPrimes;
}
// Function to count unordered pairs of
// semi prime numbers with prime sum
int countPairs(vector<int> semiPrimes)
{
// Stores the final count
int cnt = 0;
// Loop to iterate over all the
// l unordered pairs
for (int i = 0;
i < semiPrimes.size(); i++) {
for (int j = i + 1;
j < semiPrimes.size(); j++) {
// If sum of current semi prime
// numbers is a prime number
if (prime[semiPrimes[i]
+ semiPrimes[j]]
== 0) {
cnt++;
}
}
}
// Return answer
return cnt;
}
// Driver Code
int main()
{
int N = 100;
cout << countPairs(semiPrimes(N));
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
static int maxn = 100000;
// Stores the count of distinct prime
// number in factor of current number
static int[] prime = new int[maxn + 1];
// Function to return the vector of
// semi prime numbers in range [1, N]
static ArrayList<Integer> semiPrimes(int N)
{
// Count of distinct prime number
// in the factor of current number
// using Sieve of Eratosthenes
for (int p = 2; p <= maxn; p++) {
// If current number is prime
if (prime[p] == 0) {
for (int i = 2 * p; i <= maxn; i += p)
prime[i]++;
}
}
// Stores the semi prime numbers
ArrayList<Integer> sPrimes
= new ArrayList<Integer>();
for (int p = 2; p <= N; p++)
// If p has 2 distinct prime factors
if (prime[p] == 2)
sPrimes.add(p);
// Return vector
return sPrimes;
}
// Function to count unordered pairs of
// semi prime numbers with prime sum
static int countPairs(ArrayList<Integer> semiPrimes)
{
// Stores the final count
int cnt = 0;
// Loop to iterate over all the
// l unordered pairs
for (int i = 0; i < semiPrimes.size(); i++) {
for (int j = i + 1; j < semiPrimes.size(); j++) {
// If sum of current semi prime
// numbers is a prime number
if (prime[semiPrimes.get(i) + semiPrimes.get(j)] == 0) {
cnt++;
}
}
}
// Return answer
return cnt;
}
// Driver Code
public static void main(String[] args)
{
int N = 100;
System.out.print(countPairs(semiPrimes(N)));
}
}
// This code is contributed by code_hunt.
Python3
# python program of the above approach maxn = 100000 # Stores the count of distinct prime # number in factor of current number prime = [0 for _ in range(maxn)] # Function to return the vector of # semi prime numbers in range [1, N] def semiPrimes(N): # Count of distinct prime number # in the factor of current number # using Sieve of Eratosthenes for p in range(2, maxn): # If current number is prime if (prime[p] == 0): for i in range(2*p, maxn, p): prime[i] += 1 # Stores the semi prime numbers sPrimes = [] for p in range(2, N+1): # If p has 2 distinct prime factors if (prime[p] == 2): sPrimes.append(p) # Return vector return sPrimes # Function to count unordered pairs of # semi prime numbers with prime sum def countPairs(semiPrimes): # Stores the final count cnt = 0 # Loop to iterate over all the # l unordered pairs for i in range(0, len(semiPrimes)): for j in range(i+1, len(semiPrimes)): # If sum of current semi prime # numbers is a prime number if (prime[semiPrimes[i] + semiPrimes[j]] == 0): cnt += 1 # Return answer return cnt # Driver Code if __name__ == "__main__": N = 100 print(countPairs(semiPrimes(N))) # This code is contributed by rakeshsahni
C#
// C# program of the above approach
using System;
using System.Collections.Generic;
class GFG {
const int maxn = 100000;
// Stores the count of distinct prime
// number in factor of current number
static int[] prime = new int[maxn + 1];
// Function to return the vector of
// semi prime numbers in range [1, N]
static List<int> semiPrimes(int N)
{
// Count of distinct prime number
// in the factor of current number
// using Sieve of Eratosthenes
for (int p = 2; p <= maxn; p++) {
// If current number is prime
if (prime[p] == 0) {
for (int i = 2 * p; i <= maxn; i += p)
prime[i]++;
}
}
// Stores the semi prime numbers
List<int> sPrimes = new List<int>();
for (int p = 2; p <= N; p++)
// If p has 2 distinct prime factors
if (prime[p] == 2)
sPrimes.Add(p);
// Return vector
return sPrimes;
}
// Function to count unordered pairs of
// semi prime numbers with prime sum
static int countPairs(List<int> semiPrimes)
{
// Stores the final count
int cnt = 0;
// Loop to iterate over all the
// l unordered pairs
for (int i = 0; i < semiPrimes.Count; i++) {
for (int j = i + 1; j < semiPrimes.Count; j++) {
// If sum of current semi prime
// numbers is a prime number
if (prime[semiPrimes[i] + semiPrimes[j]]
== 0) {
cnt++;
}
}
}
// Return answer
return cnt;
}
// Driver Code
public static void Main()
{
int N = 100;
Console.WriteLine(countPairs(semiPrimes(N)));
}
}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript Program to implement
// the above approach
const maxn = 100000;
// Stores the count of distinct prime
// number in factor of current number
let prime = new Array(maxn).fill(0);
// Function to return the vector of
// semi prime numbers in range [1, N]
function semiPrimes(N) {
// Count of distinct prime number
// in the factor of current number
// using Sieve of Eratosthenes
for (let p = 2; p <= maxn; p++) {
// If current number is prime
if (prime[p] == 0) {
for (let i = 2 * p; i <= maxn; i += p)
prime[i]++;
}
}
// Stores the semi prime numbers
let sPrimes = [];
for (let p = 2; p <= N; p++)
// If p has 2 distinct prime factors
if (prime[p] == 2)
sPrimes.push(p);
// Return vector
return sPrimes;
}
// Function to count unordered pairs of
// semi prime numbers with prime sum
function countPairs(semiPrimes) {
// Stores the final count
let cnt = 0;
// Loop to iterate over all the
// l unordered pairs
for (let i = 0;
i < semiPrimes.length; i++) {
for (let j = i + 1;
j < semiPrimes.length; j++) {
// If sum of current semi prime
// numbers is a prime number
if (prime[semiPrimes[i]
+ semiPrimes[j]]
== 0) {
cnt++;
}
}
}
// Return answer
return cnt;
}
// Driver Code
let N = 100;
document.write(countPairs(semiPrimes(N)));
// This code is contributed by Potta Lokesh
</script>
Producción:
313
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)