Given a range of integer from ‘a’ to ‘b’ . Our task is to calculate the amount of numbers from the interval [ a, b ], that are not divisible by any number between 2 and k – 1 and yet divisible by k .
Note : We do not have to consider a divisor equal to one.
Examples:
Input : a = 12, b = 23, k = 3 Output : 2 Between [12, 23], 15 and 21 are the only number which are divisible k and not divisible by any number between 2 and k - 1. Input : a = 1, b = 80, k = 7 Output : 3
Approach : Below is the step by step algorithm to solve this problem:
- A number is divisible only by k and not by any number less than k only if k is a prime number.
- Traverse through each number from a to b to check if the number has the smallest factor as a prime number k.
- Count all such numbers in the range whose smallest factor is a prime number k.
Below is the implementation of the above approach:
C++
// C++ program to find the count of numbers in a range// whose smallest factor is K#include <bits/stdc++.h>using namespace std;// Function to check if k is a prime number or notbool isPrime(int k){ // Corner case if (k <= 1) return false; // Check from 2 to n-1 for (int i = 2; i < k; i++) if (k % i == 0) return false; return true;}// Function to check if a number is not divisible// by any number between 2 and K-1int check(int num, int k){ int flag = 1; // to check if the num is divisible by // any numbers between 2 and k - 1 for (int i = 2; i < k; i++) { if (num % i == 0) flag = 0; } if (flag == 1) { // if not divisible by any number between // 2 and k - 1 // but divisible by k if (num % k == 0) return 1; else return 0; } else return 0;}// Function to find count of numbers in range [a, b]// with smallest factor as Kint findCount(int a, int b, int k){ int count = 0; // a number can be divisible only by k and // not by any number less than k only // if k is a prime if (!isPrime(k)) return 0; else { int ans; for (int i = a; i <= b; i++) { // to check if a number has // smallest factor as K ans = check(i, k); if (ans == 1) count++; else continue; } } return count;}// Driver codeint main(){ int a = 2020, b = 6300, k = 29; cout << findCount(a, b, k); return 0;} |
Java
// Java program to find the count of numbers in a range// whose smallest factor is Kpublic class GFG { // Function to check if k is a prime number or not static boolean isPrime(int k) { // Corner case if (k <= 1) return false; // Check from 2 to n-1 for (int i = 2; i < k; i++) if (k % i == 0) return false; return true; } // Function to check if a number is not divisible // by any number between 2 and K-1 static int check(int num, int k) { int flag = 1; // to check if the num is divisible by // any numbers between 2 and k - 1 for (int i = 2; i < k; i++) { if (num % i == 0) flag = 0; } if (flag == 1) { // if not divisible by any number between // 2 and k - 1 // but divisible by k if (num % k == 0) return 1; else return 0; } else return 0; } // Function to find count of numbers in range [a, b] // with smallest factor as K static int findCount(int a, int b, int k) { int count = 0; // a number can be divisible only by k and // not by any number less than k only // if k is a prime if (!isPrime(k)) return 0; else { int ans; for (int i = a; i <= b; i++) { // to check if a number has // smallest factor as K ans = check(i, k); if (ans == 1) count++; else continue; } } return count; }// Driver codepublic static void main(String args[]) { int a = 2020, b = 6300, k = 29; System.out.println(findCount(a, b, k)); } // This Code is contributed by ANKITRAI1} |
Python 3
# Python 3 program to find the count # of numbers in a range whose smallest# factor is K# Function to check if k is # a prime number or notdef isPrime( k): # Corner case if (k <= 1): return False # Check from 2 to n-1 for i in range(2, k): if (k % i == 0): return false return True# Function to check if a number # is not divisible by any number# between 2 and K-1def check(num, k): flag = 1 # to check if the num is divisible # by any numbers between 2 and k - 1 for i in range(2, k) : if (num % i == 0): flag = 0 if (flag == 1) : # if not divisible by any # number between 2 and k - 1 # but divisible by k if (num % k == 0): return 1 else: return 0 else: return 0# Function to find count of # numbers in range [a, b] # with smallest factor as Kdef findCount(a, b, k): count = 0 # a number can be divisible only # by k and not by any number # less than k only if k is a prime if (not isPrime(k)): return 0 else : for i in range(a, b + 1) : # to check if a number has # smallest factor as K ans = check(i, k) if (ans == 1): count += 1 else: continue return count# Driver codeif __name__ == "__main__": a = 2020 b = 6300 k = 29 print(findCount(a, b, k))# This code is contributed # by ChitraNayal |
C#
// C# program to find the count // of numbers in a range whose// smallest factor is Kusing System;class GFG{// Function to check if k is // a prime number or notstatic bool isPrime(int k){ // Corner case if (k <= 1) return false; // Check from 2 to n-1 for (int i = 2; i < k; i++) if (k % i == 0) return false; return true;}// Function to check if a number // is not divisible by any number// between 2 and K-1static int check(int num, int k){ int flag = 1; // to check if the num is divisible by // any numbers between 2 and k - 1 for (int i = 2; i < k; i++) { if (num % i == 0) flag = 0; } if (flag == 1) { // if not divisible by any // number between 2 and k - 1 // but divisible by k if (num % k == 0) return 1; else return 0; } else return 0;}// Function to find count of // numbers in range [a, b]// with smallest factor as Kstatic int findCount(int a, int b, int k){ int count = 0; // a number can be divisible only // by k and not by any number less // than k only if k is a prime if (!isPrime(k)) return 0; else { int ans; for (int i = a; i <= b; i++) { // to check if a number has // smallest factor as K ans = check(i, k); if (ans == 1) count++; else continue; } } return count;}// Driver codepublic static void Main(){ int a = 2020, b = 6300, k = 29; Console.WriteLine(findCount(a, b, k));}}// This code is contributed // by Akanksha Rai(Abby_akku) |
PHP
<?php// PHP program to find the count // of numbers in a range whose // smallest factor is K// Function to check if k is// a prime number or notfunction isPrime($k){ // Corner case if ($k <= 1) return false; // Check from 2 to n-1 for ($i = 2; $i < $k; $i++) if ($k % $i == 0) return false; return true;}// Function to check if a number // is not divisible by any number // between 2 and K-1function check($num, $k){ $flag = 1; // to check if the num is divisible // by any numbers between 2 and k - 1 for ($i = 2; $i < $k; $i++) { if ($num % $i == 0) $flag = 0; } if ($flag == 1) { // if not divisible by any // number between 2 and k - 1 // but divisible by k if ($num % $k == 0) return 1; else return 0; } else return 0;}// Function to find count of // numbers in range [a, b]// with smallest factor as Kfunction findCount($a, $b, $k){ $count = 0; // a number can be divisible // only by k and not by any // number less than k only // if k is a prime if (!isPrime($k)) return 0; else { for ($i = $a; $i <= $b; $i++) { // to check if a number has // smallest factor as K $ans = check($i, $k); if ($ans == 1) $count++; else continue; } } return $count;}// Driver code$a = 2020;$b = 6300;$k = 29;echo (findCount($a, $b, $k));// This code is contributed // by Shivi_Aggarwal?> |
Javascript
<script>// Javascript program to find the count of numbers in a range// whose smallest factor is K // Function to check if k is a prime number or not function isPrime(k) { // Corner case if (k <= 1) return false; // Check from 2 to n-1 for (let i = 2; i < k; i++) if (k % i == 0) return false; return true; } // Function to check if a number is not divisible // by any number between 2 and K-1 function check(num,k) { let flag = 1; // to check if the num is divisible by // any numbers between 2 and k - 1 for (let i = 2; i < k; i++) { if (num % i == 0) flag = 0; } if (flag == 1) { // if not divisible by any number between // 2 and k - 1 // but divisible by k if (num % k == 0) return 1; else return 0; } else return 0; } // Function to find count of numbers in range [a, b] // with smallest factor as K function findCount(a,b,k) { let count = 0; // a number can be divisible only by k and // not by any number less than k only // if k is a prime if (!isPrime(k)) return 0; else { let ans; for (let i = a; i <= b; i++) { // to check if a number has // smallest factor as K ans = check(i, k); if (ans == 1) count++; else continue; } } return count; } // Driver code let a = 2020, b = 6300, k = 29; document.write(findCount(a, b, k)); // This code is contributed by avanitrachhadiya2155</script> |
Output:
28
Time Complexity : O(b-a)*k
Auxiliary Space : O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
