Find groups in given range having at least K consecutive composite integers
Given a range [L, R] and an integer K, find all the groups in the given range having at least K consecutive composite integers.
Example:
Input: L = 500, R = 650, K = 10
Output:
510 520 11
524 540 17
620 630 11
Explanation:
Prime number between 500 to 650 are
{503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647}.
So between them the consecutive composite number which are greater than K are 510-520, 524-540 and 620-630.Input: L = 10, R = 18, K = 2
Output:
14 16 3
Brute Approach: A simple solution would be to traverse all numbers in a given range and:
- Check if each number is prime or not.
- Keep a count of consecutive composite numbers.
- Print the group range with its count if the value exceeds K.
Time Complexity: O((R-L)*√R)
Auxiliary Space: O(1)
Efficient Approach: Instead of finding all the consecutive composite numbers, we can use the Alternate Hypothesis to find prime numbers in a given range and solve the problem efficiently.
An efficient solution would be to use the Sieve of Eratosthenes to find the primes and check the range between them.
Follow the steps mentioned below to implement the above approach:
- Generate the prime numbers between the range.
- After generating the prime numbers array, traverse the array.
- Check if the consecutive composite numbers exceed more than 10.
Below is the implementation of the above approach:
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 >= K) 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
Time Complexity: O(R*log(log(R)))
Auxiliary Space: O(R)
Contact Us