Given two positive integers L and R, the task is to find the count of numbers in the range [L, R] which are not divisible by any of the first K prime numbers.
Input: L = 10, R = 25, K = 3
Output: 5
Explanation: In the given range there are 5 numbers 11, 13, 17, 19, 23 which are not divisible by any of the first 3 prime numbers.
So the count is 5.Input: L = 50, R = 1000, K = 5
Output: 196
Approach: The given problem can be solved using the following idea:
First store the first K prime numbers and then traverse for all the numbers in the range [L, R] and check if they are divisible by any of the first K prime numbers or not
- Store the K prime numbers in a vector by using the Sieve of Eratosthenes.
- Then for all the K prime numbers, iterate a loop and mark all the multiples of that prime number in the L to R as divisible by any of the first K prime numbers.
- After this iterate a loop and count the numbers which are marked as not divisible in the L to R.
- The final count is the required answer.
Below is the implementation of the above approach.
C++
// C++ code to implement above approach#include <bits/stdc++.h>using namespace std;// Code for Sieve of Eratosthenes// to store first k prime numbersvoid SieveOfEratosthenes(int n, vector<int>& v, int k){ bool prime[n + 1]; memset(prime, true, sizeof(prime)); for (int i = 2; i * i <= n; i++) { if (prime[i]) { for (int j = i * i; j <= n; j += i) prime[j] = false; } } // Storing first k prime numbers // in vector v. for (int i = 2; i < n; i++) { if (prime[i]) { v.push_back(i); } if (v.size() == k) { break; } }}// Function to return the count// of numbers in range L and R// which is not divisible by first// k prime numbersint total_count(int L, int R, int k){ vector<int> v; // Calling sieve of eratosthenes SieveOfEratosthenes(100000, v, k); // Initialising the array int arr[R + 1] = { 0 }; // Making all the multiples of // every prime number in the // array arr as 1. for (int i = 0; i < v.size(); i++) { // Val is the first multiple // of v[i] which is greater // or equal to L. int val; if (L % v[i] == 0) { val = L; } else { val = ((L / v[i]) + 1) * v[i]; } for (int j = val; j <= R; j = j + v[i]) { arr[j] = 1; } } int count = 0; for (int i = L; i <= R; i++) { if (arr[i] == 0) { count++; } } return count;}// Driver codeint main(){ int L = 10, R = 25; int K = 3; // Function call cout << total_count(L, R, K); return 0;} |
Java
// Java code to implement above approachimport java.io.*;import java.util.Vector;class GFG { // Code for Sieve of Eratosthenes // to store first k prime numbers static void SieveOfEratosthenes(int n, Vector<Integer> v, int k) { boolean[] prime = new boolean[n + 1]; for(int i = 0; i < n + 1; i++) prime[i] = true; for (int i = 2; i * i <= n; i++) { if (prime[i]) { for (int j = i * i; j <= n; j += i) prime[j] = false; } } // Storing first k prime numbers // in vector v. for (int i = 2; i < n; i++) { if (prime[i]) { v.add(i); } if (v.size() == k) { break; } } } // Function to return the count // of numbers in range L and R // which is not divisible by first // k prime numbers static int total_count(int L, int R, int k) { Vector<Integer> v = new Vector<>(); // Calling sieve of eratosthenes SieveOfEratosthenes(100000, v, k); // Initialising the array int[] arr = new int[R + 1]; // Making all the multiples of // every prime number in the // array arr as 1. for (int i = 0; i < v.size(); i++) { // Val is the first multiple // of v[i] which is greater // or equal to L. int val; if (L % v.get(i) == 0) { val = L; } else { val = ((L / v.get(i)) + 1) * v.get(i); } for (int j = val; j <= R; j = j + v.get(i)) { arr[j] = 1; } } int count = 0; for (int i = L; i <= R; i++) { if (arr[i] == 0) { count++; } } return count; } // Driver code public static void main (String[] args) { int L = 10, R = 25; int K = 3; // Function call System.out.print(total_count(L, R, K)); }}// This code is contributed by hrithikgarg03188. |
Python3
# python3 code to implement above approachimport math# Code for Sieve of Eratosthenes# to store first k prime numbersdef SieveOfEratosthenes(n, v, k): prime = [True for _ in range(n + 1)] for i in range(2, int(math.sqrt(n)) + 1): if (prime[i]): for j in range(i*i, n + 1, i): prime[j] = False # Storing first k prime numbers # in vector v. for i in range(2, n): if (prime[i]): v.append(i) if (len(v) == k): break# Function to return the count# of numbers in range L and R# which is not divisible by first# k prime numbersdef total_count(L, R, k): v = [] # Calling sieve of eratosthenes SieveOfEratosthenes(100000, v, k) # Initialising the array arr = [0 for _ in range(R + 1)] # Making all the multiples of # every prime number in the # array arr as 1. for i in range(0, len(v)): # Val is the first multiple # of v[i] which is greater # or equal to L. val = 0 if (L % v[i] == 0): val = L else: val = ((L // v[i]) + 1) * v[i] for j in range(val, R + 1, v[i]): arr[j] = 1 count = 0 for i in range(L, R+1): if (arr[i] == 0): count += 1 return count# Driver codeif __name__ == "__main__": L, R = 10, 25 K = 3 # Function call print(total_count(L, R, K)) # This code is contributed by rakeshsahni |
C#
// C# code to implement above approachusing System;using System.Collections.Generic;class GFG { // Code for Sieve of Eratosthenes // to store first k prime numbers static void SieveOfEratosthenes(int n, List<int> v, int k) { bool[] prime = new bool[n + 1]; for (int i = 0; i < n + 1; i++) prime[i] = true; for (int i = 2; i * i <= n; i++) { if (prime[i]) { for (int j = i * i; j <= n; j += i) prime[j] = false; } } // Storing first k prime numbers // in vector v. for (int i = 2; i < n; i++) { if (prime[i]) { v.Add(i); } if (v.Count == k) { break; } } } // Function to return the count // of numbers in range L and R // which is not divisible by first // k prime numbers static int total_count(int L, int R, int k) { List<int> v = new List<int>(); // Calling sieve of eratosthenes SieveOfEratosthenes(100000, v, k); // Initialising the array int[] arr = new int[R + 1]; // Making all the multiples of // every prime number in the // array arr as 1. for (int i = 0; i < v.Count; i++) { // Val is the first multiple // of v[i] which is greater // or equal to L. int val; if (L % v[i] == 0) { val = L; } else { val = ((L / v[i]) + 1) * v[i]; } for (int j = val; j <= R; j = j + v[i]) { arr[j] = 1; } } int count = 0; for (int i = L; i <= R; i++) { if (arr[i] == 0) { count++; } } return count; } // Driver code public static void Main(string[] args) { int L = 10, R = 25; int K = 3; Console.Write(total_count(L, R, K)); }}// This code is contributed by ukasp. |
Javascript
<script>// JavaScript code for the above approach// Code for Sieve of Eratosthenes// to store first k prime numbersfunction SieveOfEratosthenes(n, v, k){ let prime= new Array(n+1).fill(true); for (let i = 2; i * i <= n; i++) { if (prime[i]) { for (let j = i * i; j <= n; j += i) prime[j] = false; } } // Storing first k prime numbers // in vector v. for (let i = 2; i < n; i++) { if (prime[i]) { v.push(i); } if (v.length == k) { break; } }}// Function to return the count// of numbers in range L and R// which is not divisible by first// k prime numbersfunction total_count( L, R, k){ let v =[]; // Calling sieve of eratosthenes SieveOfEratosthenes(100000, v, k); // Initialising the array let arr = new Array(R+1).fill(0); // Making all the multiples of // every prime number in the // array arr as 1. for (let i = 0; i < v.length; i++) { // Val is the first multiple // of v[i] which is greater // or equal to L. let val; if (L % v[i] == 0) { val = L; } else { val = (Math.floor(L / v[i]) + 1) * v[i]; } for (let j = val; j <= R; j = j + v[i]) { arr[j] = 1; } } let count = 0; for (let i = L; i <= R; i++) { if (arr[i] == 0) { count++; } } return count;}// Driver code let L = 10, R = 25; let K = 3; // Function call document.write(total_count(L, R, K)); // This code is contributed by Potta Lokesh </script> |
Output
5
Time complexity: O(N*log(log(N)) + K*R) where N is a high positive value
Auxiliary Space: O(N+R)
Share your thoughts in the comments
