Dado un rango [L, R] y un entero K , encuentre todos los grupos en el rango dado que tengan al menos K enteros compuestos consecutivos.
Ejemplo:
Entrada: L = 500, R = 650, K = 10
Salida:
510 520 11
524 540 17
620 630 11
Explicación:
Los números primos entre 500 y 650 son
{503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647}.
Entonces, entre ellos, los números compuestos consecutivos que son mayores que K son 510-520, 524-540 y 620-630.Entrada: L = 10, R = 18, K = 2
Salida:
14 16 3
Enfoque bruto: una solución simple sería atravesar todos los números en un rango dado y:
- Comprueba si cada número es primo o no.
- Mantenga un conteo de números compuestos consecutivos.
- Imprime el rango del grupo con su conteo si el valor excede K .
Complejidad de Tiempo: O((RL)*√R)
Espacio Auxiliar: O(1)
Enfoque eficiente: en lugar de encontrar todos los números compuestos consecutivos, podemos usar la hipótesis alternativa para encontrar números primos en un rango determinado y resolver el problema de manera eficiente.
Una solución eficiente sería utilizar la Tamiz de Eratóstenes para encontrar los números primos y comprobar el rango entre ellos.
Siga los pasos mencionados a continuación para implementar el enfoque anterior:
- Genera los números primos entre el rango.
- Después de generar la array de números primos, recorra la array.
- Compruebe si los números compuestos consecutivos superan más de 10.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the range
void Composite_range(int l, int r, int K)
{
// Code of sieve of Eratosthenes
int n = r;
bool prime[n + 1] = { false };
for (int i = 0; i <= n; i++)
prime[i] = true;
for (int p = 2; p * p <= n; p++) {
// If prime[p] is not changed,
// then it is a prime
if (prime[p] == true) {
// Update all multiples of p
for (int i = p * p; i <= n; i += p)
prime[i] = false;
}
}
int count = 0;
for (int i = l; i <= r; i++) {
// If the number is a prime then
// check whether the previous consecutive
// composite number count is
// greater than K
if (prime[i] == true) {
if (count >= K)
cout << (i - count) << " "
<< i - 1 << " "
<< count << "\n";
count = 0;
}
else
count++;
}
if (count >= 10)
cout << (r - count) << " "
<< r << " " << count
<< "\n";
}
// Driver Code
int main()
{
int L = 500;
int R = 650;
int K = 10;
// Function call
Composite_range(L, R, K);
return 0;
}
Java
// Java code to implement the approach
import java.util.*;
public class GFG {
// Function to find the range
static void Composite_range(int l, int r, int K)
{
// Code of sieve of Eratosthenes
int n = r;
boolean[] prime = new boolean[n + 1];
for (int i = 0; i <= n; i++)
prime[i] = true;
for (int p = 2; p * p <= n; p++) {
// If prime[p] is not changed,
// then it is a prime
if (prime[p] == true) {
// Update all multiples of p
for (int i = p * p; i <= n; i += p)
prime[i] = false;
}
}
int count = 0;
for (int i = l; i <= r; i++) {
// If the number is a prime then
// check whether the previous consecutive
// composite number count is
// greater than K
if (prime[i] == true) {
if (count >= K)
System.out.println((i - count) + " "
+ (i - 1) + " "
+ count);
count = 0;
}
else
count++;
}
if (count >= 10)
System.out.println((r - count) + " " + r + " "
+ count);
}
// Driver Code
public static void main(String args[])
{
int L = 500;
int R = 650;
int K = 10;
// Function call
Composite_range(L, R, K);
}
}
// This code is contributed by Samim Hossain Mondal.
Python3
# python3 code to implement the approach
from cmath import sqrt
import math
# Function to find the range
def Composite_range(l, r, K):
# Code of sieve of Eratosthenes
n = r
prime = [False for _ in range(n + 1)]
for i in range(0, n+1):
prime[i] = True
for p in range(2, int(math.sqrt(n)) + 1):
# If prime[p] is not changed,
# then it is a prime
if (prime[p] == True):
# Update all multiples of p
for i in range(p*p, n+1, p):
prime[i] = False
count = 0
for i in range(l, r + 1):
# If the number is a prime then
# check whether the previous consecutive
# composite number count is
# greater than K
if (prime[i] == True):
if (count >= K):
print(f"{(i - count)} {i - 1} {count}")
count = 0
else:
count += 1
if (count >= 10):
print(f"{(r - count)} {r} {count}")
# Driver Code
if __name__ == "__main__":
L = 500
R = 650
K = 10
# Function call
Composite_range(L, R, K)
# This code is contributed by rakeshsahni
C#
// C# code to implement the approach
using System;
class GFG {
// Function to find the range
static void Composite_range(int l, int r, int K)
{
// Code of sieve of Eratosthenes
int n = r;
bool[] prime = new bool[n + 1];
for (int i = 0; i <= n; i++)
prime[i] = true;
for (int p = 2; p * p <= n; p++) {
// If prime[p] is not changed,
// then it is a prime
if (prime[p] == true) {
// Update all multiples of p
for (int i = p * p; i <= n; i += p)
prime[i] = false;
}
}
int count = 0;
for (int i = l; i <= r; i++) {
// If the number is a prime then
// check whether the previous consecutive
// composite number count is
// greater than K
if (prime[i] == true) {
if (count >= K)
Console.WriteLine((i - count) + " "
+ (i - 1) + " "
+ count);
count = 0;
}
else
count++;
}
if (count >= 10)
Console.WriteLine((r - count) + " " + r + " "
+ count);
}
// Driver Code
public static void Main()
{
int L = 500;
int R = 650;
int K = 10;
// Function call
Composite_range(L, R, K);
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript code for the above approach
// Function to find the range
function Composite_range(l, r, K) {
// Code of sieve of Eratosthenes
let n = r;
let prime = new Array(n + 1).fill(false);
for (let i = 0; i <= n; i++)
prime[i] = true;
for (let p = 2; p * p <= n; p++) {
// If prime[p] is not changed,
// then it is a prime
if (prime[p] == true) {
// Update all multiples of p
for (let i = p * p; i <= n; i += p)
prime[i] = false;
}
}
let count = 0;
for (let i = l; i <= r; i++) {
// If the number is a prime then
// check whether the previous consecutive
// composite number count is
// greater than K
if (prime[i] == true) {
if (count >= K)
document.write((i - count) + " "
+ (i - 1) + " "
+ count + "<br>");
count = 0;
}
else
count++;
}
if (count >= 10)
document.write((r - count) + " "
+ r + " " + count
+ "<br>");
}
// Driver Code
let L = 500;
let R = 650;
let K = 10;
// Function call
Composite_range(L, R, K);
// This code is contributed by Potta Lokesh
</script>
510 520 11 524 540 17 620 630 11
Complejidad de tiempo : O(R*log(log(R)))
Espacio auxiliar : O(R)
Publicación traducida automáticamente
Artículo escrito por manishguptagkp06 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA