Dados dos enteros A y B y un entero N . La tarea es encontrar N números primos de la forma A + nB o B + nA ( n =1, 2, 3…). Si no es posible, imprima -1.
Ejemplos:
Entrada: A = 3, B = 5, N = 4
Salida: 13, 11, 17, 23
Explicación:
13 (3+2*5)
11 (5+2*3)
17 (5+4*3)
23 ( 3+4*5)Entrada: A = 4, B = 6, N = 4
Salida: -1
Enfoque:
dado que A + nB es un número primo, una cosa es segura: no debe haber ningún factor común entre A y B , lo que significa que A y B deben ser coprimos.
El mejor y más eficiente enfoque será utilizar el teorema de Dirichlet .
El teorema de Dirichlet dice que si a y b son números primos positivos relativos, entonces la secuencia aritmética a , a + b , a + 2b , a + 3b … contiene infinitos números primos.
Entonces, en primer lugar, verifique si A y B son coprimos.
Si A y B son primos coprimos, comprueba la primalidad de A + nB y B + nA , donde n = 1, 2, 3… Imprime los primeros N números primos entre ellos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Utility function to check
// whether two numbers is
// co-prime or not
int coprime(int a, int b)
{
if (__gcd(a, b) == 1)
return true;
else
return false;
}
// Utility function to check
// whether a number is prime
// or not
bool isPrime(int n)
{
// Corner case
if (n <= 1)
return false;
if (n == 2 or n == 3)
return true;
// Check from 2 to sqrt(n)
for (int i = 2; i * i <= n; i++)
if (n % i == 0)
return false;
return true;
}
// finding the Prime numbers
void findNumbers(int a, int b, int n)
{
bool possible = true;
// Checking whether given
// numbers are co-prime
// or not
if (!coprime(a, b))
possible = false;
int c1 = 1;
int c2 = 1;
int num1, num2;
// To store the N primes
set<int> st;
// If 'possible' is true
if (possible) {
// Printing n numbers
// of prime
while ((int)st.size() != n) {
// checking the form of a+nb
num1 = a + (c1 * b);
if (isPrime(num1)) {
st.insert(num1);
}
c1++;
// Checking the form of b+na
num2 = b + (c2 * a);
if (isPrime(num2)) {
st.insert(num2);
}
c2++;
}
for (int i : st)
cout << i << " ";
}
// If 'possible' is false
// return -1
else
cout << "-1";
}
// Driver Code
int main()
{
int a = 3;
int b = 5;
int n = 4;
findNumbers(a, b, n);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
static int __gcd(int a, int b)
{
if (b == 0)
return a;
return __gcd(b, a % b);
}
// Utility function to check
// whether two numbers is
// co-prime or not
static boolean coprime(int a, int b)
{
if (__gcd(a, b) == 1)
return true;
else
return false;
}
// Utility function to check
// whether a number is prime
// or not
static boolean isPrime(int n)
{
// Corner case
if (n <= 1)
return false;
if (n == 2 || n == 3)
return true;
// Check from 2 to sqrt(n)
for (int i = 2; i * i <= n; i++)
if (n % i == 0)
return false;
return true;
}
// finding the Prime numbers
static void findNumbers(int a, int b, int n)
{
boolean possible = true;
// Checking whether given
// numbers are co-prime
// or not
if (!coprime(a, b))
possible = false;
int c1 = 1;
int c2 = 1;
int num1, num2;
// To store the N primes
HashSet<Integer> st = new HashSet<Integer>();
// If 'possible' is true
if (possible)
{
// Printing n numbers
// of prime
while ((int)st.size() != n)
{
// checking the form of a+nb
num1 = a + (c1 * b);
if (isPrime(num1))
{
st.add(num1);
}
c1++;
// Checking the form of b+na
num2 = b + (c2 * a);
if (isPrime(num2))
{
st.add(num2);
}
c2++;
}
for (int i : st)
System.out.print(i + " ");
}
// If 'possible' is false
// return -1
else
System.out.print("-1");
}
// Driver Code
public static void main(String[] args)
{
int a = 3;
int b = 5;
int n = 4;
findNumbers(a, b, n);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation of the above approach
from math import gcd, sqrt
# Utility function to check
# whether two numbers is
# co-prime or not
def coprime(a, b) :
if (gcd(a, b) == 1) :
return True;
else :
return False;
# Utility function to check
# whether a number is prime
# or not
def isPrime(n) :
# Corner case
if (n <= 1) :
return False;
if (n == 2 or n == 3) :
return True;
# Check from 2 to sqrt(n)
for i in range(2, int(sqrt(n)) + 1) :
if (n % i == 0) :
return False;
return True;
# finding the Prime numbers
def findNumbers(a, b, n) :
possible = True;
# Checking whether given
# numbers are co-prime
# or not
if (not coprime(a, b)) :
possible = False;
c1 = 1;
c2 = 1;
num1 = 0;
num2 = 0;
# To store the N primes
st = set();
# If 'possible' is true
if (possible) :
# Printing n numbers
# of prime
while (len(st) != n) :
# checking the form of a+nb
num1 = a + (c1 * b);
if (isPrime(num1)):
st.add(num1);
c1 += 1;
# Checking the form of b+na
num2 = b + (c2 * a);
if (isPrime(num2)):
st.add(num2);
c2 += 1;
for i in st :
print(i, end = " ");
# If 'possible' is false
# return -1
else :
print("-1");
# Driver Code
if __name__ == "__main__" :
a = 3;
b = 5;
n = 4;
findNumbers(a, b, n);
# This code is contributed by AnkitRai01
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
static int __gcd(int a, int b)
{
if (b == 0)
return a;
return __gcd(b, a % b);
}
// Utility function to check
// whether two numbers is
// co-prime or not
static bool coprime(int a, int b)
{
if (__gcd(a, b) == 1)
return true;
else
return false;
}
// Utility function to check
// whether a number is prime
// or not
static bool isPrime(int n)
{
// Corner case
if (n <= 1)
return false;
if (n == 2 || n == 3)
return true;
// Check from 2 to sqrt(n)
for (int i = 2; i * i <= n; i++)
if (n % i == 0)
return false;
return true;
}
// finding the Prime numbers
static void findNumbers(int a, int b, int n)
{
bool possible = true;
// Checking whether given
// numbers are co-prime
// or not
if (!coprime(a, b))
possible = false;
int c1 = 1;
int c2 = 1;
int num1, num2;
// To store the N primes
HashSet<int> st = new HashSet<int>();
// If 'possible' is true
if (possible)
{
// Printing n numbers
// of prime
while (st.Count != n)
{
// checking the form of a+nb
num1 = a + (c1 * b);
if (isPrime(num1))
{
st.Add(num1);
}
c1++;
// Checking the form of b+na
num2 = b + (c2 * a);
if (isPrime(num2))
{
st.Add(num2);
}
c2++;
}
foreach (int i in st)
Console.Write(i + " ");
}
// If 'possible' is false
// return -1
else
Console.Write("-1");
}
// Driver Code
public static void Main(String[] args)
{
int a = 3;
int b = 5;
int n = 4;
findNumbers(a, b, n);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation of
// the above approach
function __gcd(a, b) {
if (b == 0)
return a;
return __gcd(b, a % b);
}
// Utility function to check
// whether two numbers is
// co-prime or not
function coprime(a, b) {
if (__gcd(a, b) == 1)
return true;
else
return false;
}
// Utility function to check
// whether a number is prime
// or not
function isPrime(n) {
// Corner case
if (n <= 1)
return false;
if (n == 2 || n == 3)
return true;
// Check from 2 to sqrt(n)
for (let i = 2; i * i <= n; i++)
if (n % i == 0)
return false;
return true;
}
// finding the Prime numbers
function findNumbers(a, b, n) {
let possible = true;
// Checking whether given
// numbers are co-prime
// or not
if (!coprime(a, b))
possible = false;
let c1 = 1;
let c2 = 1;
let num1, num2;
// To store the N primes
let st = new Set();
// If 'possible' is true
if (possible) {
// Printing n numbers
// of prime
while (st.size != n) {
// checking the form of a+nb
num1 = a + (c1 * b);
if (isPrime(num1)) {
st.add(num1);
}
c1++;
// Checking the form of b+na
num2 = b + (c2 * a);
if (isPrime(num2)) {
st.add(num2);
}
c2++;
}
// Sort the Set by using spread operator and Array.sort() method
st = [...st].sort((a, b) => a - b)
for (let i of st)
document.write(i + " ");
}
// If 'possible' is false
// return -1
else
document.write("-1");
}
// Driver Code
let a = 3;
let b = 5;
let n = 4;
findNumbers(a, b, n);
// This code is contributed by _saurabh_jaiswal
</script>
Producción:
11 13 17 23
Complejidad de tiempo: O(n*sqrt(n))
Espacio Auxiliar: O(n)
Publicación traducida automáticamente
Artículo escrito por dangenmaster2 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA