Dados dos enteros N y K , la tarea es encontrar el primer elemento para cada conjunto de K elementos consecutivos que tienen exactamente K factores primos y son menores que N .
Ejemplos:
Entrada: N = 30, K = 2
Salida: 14 20 21
Explicación:
Números que tienen factores primos iguales a 2 menos que 30 = { 14, 15, 18, 20, 21, 22, 24, 26, 28 }.
En los ejemplos anteriores, para K = 2 (14, 15) (20, 21) (21, 22) solo forma tales conjuntos y, por lo tanto, la serie es 14, 20, 21.
Entrada: N = 1000, K = 3
Salida: 644 740 804 986
Enfoque ingenuo: El enfoque ingenuo consiste en iterar de 2 a N y verificar que cada K número consecutivo forme un conjunto que tenga K factores primos para cada elemento del conjunto. Si la respuesta es «Sí», imprima el primer elemento de este conjunto y verifique los siguientes elementos K.
Complejidad de tiempo: O(N*K)
Espacio auxiliar: O(1)
Enfoque eficiente: El enfoque anterior se puede optimizar calculando previamente el número de factores primos hasta N y verificando que cada K elementos consecutivos cuenten con K factores primos. A continuación se muestran los pasos:
- Cree una array de factores primos más pequeña spf[] que almacene los factores primos más pequeños para cada número hasta N usando la criba de Eratóstenes .
- Usando el paso anterior, cuente el número de factores primos hasta cada número N
- Almacene el número en la array (digamos result[] ) cuya cuenta de factor primo es K .
- Para cada elemento de la array result[], compruebe si existen K números consecutivos y luego imprima el primer elemento de K números consecutivos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
#define x 2000021
using namespace std;
// For storing smallest prime factor
long long int v[x];
// Function construct smallest
// prime factor array
void sieve()
{
v[1] = 1;
// Mark smallest prime factor for
// every number to be itself.
for (long long int i = 2; i < x; i++)
v[i] = i;
// separately mark spf for every even
// number as 2
for (long long int i = 4; i < x; i += 2)
v[i] = 2;
for (long long int i = 3; i * i < x; i++) {
// Check if i is prime
if (v[i] == i) {
// Mark SPF for all numbers
// divisible by i
for (long long int j = i * i;
j < x; j += i) {
// Mark spf[j] if it is
// not previously marked
if (v[j] == j) {
v[j] = i;
}
}
}
}
}
// Function for counts total number
// of prime factors
long long int prime_factors(long long n)
{
set<long long int> s;
while (n != 1) {
s.insert(v[n]);
n = n / v[n];
}
return s.size();
}
// Function to print elements of sets
// of K consecutive elements having
// K prime factors
void distinctPrimes(long long int m,
long long int k)
{
// To store the result
vector<long long int> result;
for (long long int i = 14;
i < m + k; i++) {
// Count number of prime
// factors of number
long long count
= prime_factors(i);
// If number has exactly K
// factors push in result[]
if (count == k) {
result.push_back(i);
}
}
long long int p = result.size();
for (long long int index = 0;
index < p - 1; index++) {
long long element = result[index];
long long count = 1, z = index;
// Iterate till we get K consecutive
// elements in result[]
while (z < p - 1 && count <= k
&& result[z] + 1
== result[z + 1]) {
// Count sequence until K
count++;
z++;
}
// Print the element if count >= K
if (count >= k)
cout << element << ' ';
}
}
// Driver Code
int main()
{
// To construct spf[]
sieve();
// Given N and K
long long int N = 1000, K = 3;
// Function Call
distinctPrimes(N, K);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
static final int x = 2000021;
// For storing smallest prime factor
static int []v = new int[x];
// Function consmallest
// prime factor array
static void sieve()
{
v[1] = 1;
// Mark smallest prime factor for
// every number to be itself.
for(int i = 2; i < x; i++)
v[i] = i;
// Separately mark spf for every even
// number as 2
for(int i = 4; i < x; i += 2)
v[i] = 2;
for(int i = 3; i * i < x; i++)
{
// Check if i is prime
if (v[i] == i)
{
// Mark SPF for all numbers
// divisible by i
for(int j = i * i; j < x; j += i)
{
// Mark spf[j] if it is
// not previously marked
if (v[j] == j)
{
v[j] = i;
}
}
}
}
}
// Function for counts total number
// of prime factors
static int prime_factors(int n)
{
HashSet<Integer> s = new HashSet<Integer>();
while (n != 1)
{
s.add(v[n]);
n = n / v[n];
}
return s.size();
}
// Function to print elements of sets
// of K consecutive elements having
// K prime factors
static void distinctPrimes(int m, int k)
{
// To store the result
Vector<Integer> result = new Vector<Integer>();
for (int i = 14; i < m + k; i++)
{
// Count number of prime
// factors of number
long count = prime_factors(i);
// If number has exactly K
// factors push in result[]
if (count == k)
{
result.add(i);
}
}
int p = result.size();
for(int index = 0;
index < p - 1; index++)
{
long element = result.get(index);
int count = 1, z = index;
// Iterate till we get K consecutive
// elements in result[]
while (z < p - 1 && count <= k &&
result.get(z) + 1 ==
result.get(z + 1))
{
// Count sequence until K
count++;
z++;
}
// Print the element if count >= K
if (count >= k)
System.out.print(element + " ");
}
}
// Driver code
public static void main(String[] args)
{
// To construct spf[]
sieve();
// Given N and K
int N = 1000, K = 3;
// Function call
distinctPrimes(N, K);
}
}
// This code is contributed by Princi Singh
Python3
# Python3 program for the above approach x = 2000021 # For storing smallest prime factor v = [0] * x # Function construct smallest # prime factor array def sieve(): v[1] = 1 # Mark smallest prime factor for # every number to be itself for i in range(2, x): v[i] = i # separately mark spf for every # even number as 2 for i in range(4, x, 2): v[i] = 2 i = 3 while (i * i < x): # Check if i is prime if (v[i] == i): # Mark SPF for all numbers # divisible by i for j in range(i * i, x, i): # Mark spf[i] if it is # not previously marked if (v[j] == j): v[j] = i i += 1 # Function for counts total number # of prime factors def prime_factors(n): s = set() while (n != 1): s.add(v[n]) n = n // v[n] return len(s) # Function to print elements of sets # of K consecutive elements having # K prime factors def distinctPrimes(m, k): # To store the result result = [] for i in range(14, m + k): # Count number of prime # factors of number count = prime_factors(i) # If number has exactly K # factors push in result[] if (count == k): result.append(i) p = len(result) for index in range(p - 1): element = result[index] count = 1 z = index # Iterate till we get K consecutive # elements in result[] while (z < p - 1 and count <= k and result[z] + 1 == result[z + 1]): # Count sequence until K count += 1 z += 1 # Print the element if count >= K if (count >= k): print(element, end = ' ') # Driver Code if __name__ == '__main__': # To construct spf[] sieve() # Given N and K N = 1000 K = 3 # Function call distinctPrimes(N, K) # This code is contributed by himanshu77
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
static readonly int x = 2000021;
// For storing smallest prime factor
static int []v = new int[x];
// Function consmallest
// prime factor array
static void sieve()
{
v[1] = 1;
// Mark smallest prime factor for
// every number to be itself.
for(int i = 2; i < x; i++)
v[i] = i;
// Separately mark spf for every even
// number as 2
for(int i = 4; i < x; i += 2)
v[i] = 2;
for(int i = 3; i * i < x; i++)
{
// Check if i is prime
if (v[i] == i)
{
// Mark SPF for all numbers
// divisible by i
for(int j = i * i; j < x; j += i)
{
// Mark spf[j] if it is
// not previously marked
if (v[j] == j)
{
v[j] = i;
}
}
}
}
}
// Function for counts total number
// of prime factors
static int prime_factors(int n)
{
HashSet<int> s = new HashSet<int>();
while (n != 1)
{
s.Add(v[n]);
n = n / v[n];
}
return s.Count;
}
// Function to print elements of sets
// of K consecutive elements having
// K prime factors
static void distinctPrimes(int m, int k)
{
// To store the result
List<int> result = new List<int>();
for (int i = 14; i < m + k; i++)
{
// Count number of prime
// factors of number
long count = prime_factors(i);
// If number has exactly K
// factors push in result[]
if (count == k)
{
result.Add(i);
}
}
int p = result.Count;
for(int index = 0;
index < p - 1; index++)
{
long element = result[index];
int count = 1, z = index;
// Iterate till we get K consecutive
// elements in result[]
while (z < p - 1 && count <= k &&
result[z] + 1 == result[z + 1])
{
// Count sequence until K
count++;
z++;
}
// Print the element if count >= K
if (count >= k)
Console.Write(element + " ");
}
}
// Driver code
public static void Main(String[] args)
{
// To construct spf[]
sieve();
// Given N and K
int N = 1000, K = 3;
// Function call
distinctPrimes(N, K);
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Javascript program for the above approach
let x = 2000021
// For storing smallest prime factor
let v = new Array(x);
// Function construct smallest
// prime factor array
function sieve()
{
v[1] = 1;
// Mark smallest prime factor for
// every number to be itself.
for (let i = 2; i < x; i++)
v[i] = i;
// separately mark spf for every even
// number as 2
for (let i = 4; i < x; i += 2)
v[i] = 2;
for (let i = 3; i * i < x; i++) {
// Check if i is prime
if (v[i] == i) {
// Mark SPF for all numbers
// divisible by i
for (let j = i * i;
j < x; j += i) {
// Mark spf[j] if it is
// not previously marked
if (v[j] == j) {
v[j] = i;
}
}
}
}
}
// Function for counts total number
// of prime factors
function prime_factors(n)
{
let s = new Set();
while (n != 1) {
s.add(v[n]);
n = n / v[n];
}
return s.size;
}
// Function to print elements of sets
// of K consecutive elements having
// K prime factors
function distinctPrimes(m, k)
{
// To store the result
let result = new Array();
for (let i = 14;
i < m + k; i++) {
// Count number of prime
// factors of number
let count
= prime_factors(i);
// If number has exactly K
// factors push in result[]
if (count == k) {
result.push(i);
}
}
let p = result.length;
for (let index = 0;
index < p - 1; index++) {
let element = result[index];
let count = 1, z = index;
// Iterate till we get K consecutive
// elements in result[]
while (z < p - 1 && count <= k
&& result[z] + 1
== result[z + 1]) {
// Count sequence until K
count++;
z++;
}
// Print the element if count >= K
if (count >= k)
document.write(element + ' ');
}
}
// Driver Code
// To construct spf[]
sieve();
// Given N and K
let N = 1000, K = 3;
// Function Call
distinctPrimes(N, K);
// This code is contributed by_saurabh_jaiswal
</script>
Producción:
644 740 804 986
Complejidad de tiempo: O(N*log(log N))
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por siddhanthapliyal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA