Dada una array arr[] y el número entero Q que denota el número de consultas y dos números a, b , la tarea es encontrar el número de pares ordenados (p, q) tales que a * p + b * q = arr[i] , donde p y q son números primos.
Ejemplos:
Entrada: Q = 3, arr[] = { 2, 7, 11 }, a = 1, b = 2
Salida: 0 1 2
Explicación:
2 -> No hay pares ordenados (p, q) tales que p + 2 *q = 2.
7 -> Solo hay un par ordenado (p, q) = (3, 2) tal que p + 2*q = 7.
11 -> Hay dos pares ordenados (p, q) = ( 7, 2), (5, 3) tal que p + 2*q = 11.
Entrada: Q = 2, arr[] = { 15, 25 }, a = 1, b = 2
Salida: 2 3
Enfoque: la idea es almacenar todos los números primos en una array usando Sieve of Eratosthenes . Después de almacenar los números primos, cuente el número de pares ordenados (p, q) tales que a*p + b*q = N para cada combinación de (p, q) en la array de números primos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the number of ordered
// pairs such that a * p + b * q = N
// where p and q are primes
#include <bits/stdc++.h>
#define size 10001
using namespace std;
int prime[size];
int freq[size];
// Sieve of eratosthenes
// to store the prime numbers
// and their frequency in form a*p+b*q
void sieve(int a, int b)
{
prime[1] = 1;
// Performing Sieve of Eratosthenes
// to find the prime numbers unto 10001
for (int i = 2; i * i < size; i++) {
if (prime[i] == 0) {
for (int j = i * 2; j < size; j += i)
prime[j] = 1;
}
}
// Loop to find the number of
// ordered pairs for every combination
// of the prime numbers
for (int p = 1; p < size; p++) {
for (int q = 1; q < size; q++) {
if (prime[p] == 0 && prime[q] == 0
&& a * p + b * q < size) {
freq[a * p + b * q]++;
}
}
}
}
// Driver code
int main()
{
int queries = 2, a = 1, b = 2;
sieve(a, b);
int arr[queries] = { 15, 25 };
// Printing the number of ordered pairs
// for every query
for (int i = 0; i < queries; i++) {
cout << freq[arr[i]] << " ";
}
return 0;
}
Java
// Java program to find the number of ordered
// pairs such that a * p + b * q = N
// where p and q are primes
public class GFG {
final static int size = 10001;
static int prime[] = new int[size];
static int freq[] = new int [size];
// Sieve of eratosthenes
// to store the prime numbers
// and their frequency in form a*p+b*q
static void sieve(int a, int b)
{
prime[1] = 1;
// Performing Sieve of Eratosthenes
// to find the prime numbers unto 10001
for (int i = 2; i * i < size; i++) {
if (prime[i] == 0) {
for (int j = i * 2; j < size; j += i)
prime[j] = 1;
}
}
// Loop to find the number of
// ordered pairs for every combination
// of the prime numbers
for (int p = 1; p < size; p++) {
for (int q = 1; q < size; q++) {
if (prime[p] == 0 && prime[q] == 0
&& a * p + b * q < size) {
freq[a * p + b * q]++;
}
}
}
}
// Driver code
public static void main (String[] args)
{
int queries = 2, a = 1, b = 2;
sieve(a, b);
int arr[] = { 15, 25 };
// Printing the number of ordered pairs
// for every query
for (int i = 0; i < queries; i++) {
System.out.print(freq[arr[i]] + " ");
}
}
}
// This code is contributed by AnkitRai01
Python3
# Python3 program to find the number of ordered # pairs such that a * p + b * q = N # where p and q are primes from math import sqrt size = 1000 prime = [0 for i in range(size)] freq = [0 for i in range(size)] # Sieve of eratosthenes # to store the prime numbers # and their frequency in form a*p+b*q def sieve(a, b): prime[1] = 1 # Performing Sieve of Eratosthenes # to find the prime numbers unto 10001 for i in range(2, int(sqrt(size)) + 1, 1): if (prime[i] == 0): for j in range(i*2, size, i): prime[j] = 1 # Loop to find the number of # ordered pairs for every combination # of the prime numbers for p in range(1, size, 1): for q in range(1, size, 1): if (prime[p] == 0 and prime[q] == 0 and a * p + b * q < size): freq[a * p + b * q] += 1 # Driver code if __name__ == '__main__': queries = 2 a = 1 b = 2 sieve(a, b) arr = [15, 25] # Printing the number of ordered pairs # for every query for i in range(queries): print(freq[arr[i]],end = " ") # This code is contributed by Surendra_Gangwar
C#
// C# program to find the number of ordered
// pairs such that a * p + b * q = N
// where p and q are primes
using System;
class GFG {
static int size = 10001;
static int []prime = new int[size];
static int []freq = new int [size];
// Sieve of eratosthenes
// to store the prime numbers
// and their frequency in form a*p+b*q
static void sieve(int a, int b)
{
prime[1] = 1;
// Performing Sieve of Eratosthenes
// to find the prime numbers unto 10001
for (int i = 2; i * i < size; i++) {
if (prime[i] == 0) {
for (int j = i * 2; j < size; j += i)
prime[j] = 1;
}
}
// Loop to find the number of
// ordered pairs for every combination
// of the prime numbers
for (int p = 1; p < size; p++) {
for (int q = 1; q < size; q++) {
if (prime[p] == 0 && prime[q] == 0
&& a * p + b * q < size) {
freq[a * p + b * q]++;
}
}
}
}
// Driver code
public static void Main (string[] args)
{
int queries = 2, a = 1, b = 2;
sieve(a, b);
int []arr = { 15, 25 };
// Printing the number of ordered pairs
// for every query
for (int i = 0; i < queries; i++) {
Console.Write(freq[arr[i]] + " ");
}
}
}
// This code is contributed by AnkitRai01
Javascript
<script>
// JavaScript program to find the number of ordered
// pairs such that a * p + b * q = N
// where p and q are primes
size=10001
prime = Array(size).fill(0);
freq = Array(size).fill(0);
// Sieve of eratosthenes
// to store the prime numbers
// and their frequency in form a*p+b*q
function sieve(a, b)
{
prime[1] = 1;
// Performing Sieve of Eratosthenes
// to find the prime numbers unto 10001
for (var i = 2; i * i < size; i++) {
if (prime[i] == 0) {
for (var j = i * 2; j < size; j += i)
prime[j] = 1;
}
}
// Loop to find the number of
// ordered pairs for every combination
// of the prime numbers
for (var p = 1; p < size; p++) {
for (var q = 1; q < size; q++) {
if (prime[p] == 0 && prime[q] == 0
&& a * p + b * q < size) {
freq[a * p + b * q]++;
}
}
}
}
// Driver code
var queries = 2, a = 1, b = 2;
sieve(a, b);
var arr = [ 15, 25 ];
// Printing the number of ordered pairs
// for every query
for(var i = 0; i < queries; i++) {
document.write(freq[arr[i]] + " ");
}
</script>
Producción:
2 3
Complejidad de tiempo: O(N)
Espacio auxiliar: O (tamaño)