Given two integers N and K, the task is to find the first element for every set of K consecutive elements which have exactly K prime factors and are less than N.
Examples:
Input: N = 30, K = 2
Output: 14 20 21
Explanation:
Numbers which have prime factors equals to 2 less than 30 = { 14, 15, 18, 20, 21, 22, 24, 26, 28 }.
In the above examples, for K = 2 (14, 15) (20, 21) (21, 22) only forms such sets and therefore the series is 14, 20, 21.
Input: N = 1000, K = 3
Output: 644 740 804 986
Naive Approach: The naive approach is to iterate from 2 to N and check that every K consecutive number forms a set having K prime factors for each element in the set. If “Yes” then print the first element of this set and check for next K elements.
Time Complexity: O(N*K)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized by precomputing the number of prime factors till N and check for every K consecutive elements count having K prime factors. Below are the steps:
- Create a smallest prime factor array spf[] which stores the smallest prime factors for every number till N using Sieve of Eratosthenes.
- Using the above step, count the number of prime factors till each number N
- Store the number in the array(say result[]) whose count of prime factor is K.
- For each element of the array result[] check if there exists K consecutive numbers then print the first element of K consecutive numbers.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>#define x 2000021using namespace std;// For storing smallest prime factorlong long int v[x];// Function construct smallest// prime factor arrayvoid 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 factorslong 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 factorsvoid 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 Codeint 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 approachimport java.util.*;class GFG{ static final int x = 2000021; // For storing smallest prime factorstatic int []v = new int[x];// Function consmallest// prime factor arraystatic 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 factorsstatic 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 factorsstatic 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 codepublic 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 approachx = 2000021# For storing smallest prime factorv = [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 Codeif __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 approachusing System;using System.Collections.Generic;class GFG{ static readonly int x = 2000021; // For storing smallest prime factorstatic int []v = new int[x];// Function consmallest// prime factor arraystatic 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 factorsstatic 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 factorsstatic 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 codepublic 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 approachlet x = 2000021// For storing smallest prime factorlet v = new Array(x);// Function construct smallest// prime factor arrayfunction 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 factorsfunction 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 factorsfunction 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> |
Output:
644 740 804 986
Time Complexity: O(N*log(log N))
Auxiliary Space: O(N)
