Count numbers from range whose prime factors are only 2 and 3
Given two positive integers L and R, the task is to count the elements from the range [L, R] whose prime factors are only 2 and 3.
Examples:
Input: L = 1, R = 10
Output: 6
2 = 2
3 = 3
4 = 2 * 2
6 = 2 * 3
8 = 2 * 2 * 2
9 = 3 * 3
Input: L = 100, R = 200
Output: 5
Approach: Start a loop from L to R and for every element num:
- While num is divisible by 2, divide it by 2.
- While num is divisible by 3, divide it by 3.
- If num = 1 then increment the count as num has only 2 and 3 as its prime factors.
Print the count in the end.
Below is the implementation of the above approach:
C++
// C++ program to count the numbers within a range // whose prime factors are only 2 and 3 #include <bits/stdc++.h> using namespace std; // Function to count the number within a range // whose prime factors are only 2 and 3 int findTwoThreePrime( int l, int r) { // Start with 2 so that 1 doesn't get counted if (l == 1) l++; int count = 0; for ( int i = l; i <= r; i++) { int num = i; // While num is divisible by 2, divide it by 2 while (num % 2 == 0) num /= 2; // While num is divisible by 3, divide it by 3 while (num % 3 == 0) num /= 3; // If num got reduced to 1 then it has // only 2 and 3 as prime factors if (num == 1) count++; } return count; } // Driver code int main() { int l = 1, r = 10; cout << findTwoThreePrime(l, r); return 0; } |
Java
//Java program to count the numbers within a range // whose prime factors are only 2 and 3 import java.io.*; class GFG { // Function to count the number within a range // whose prime factors are only 2 and 3 static int findTwoThreePrime( int l, int r) { // Start with 2 so that 1 doesn't get counted if (l == 1 ) l++; int count = 0 ; for ( int i = l; i <= r; i++) { int num = i; // While num is divisible by 2, divide it by 2 while (num % 2 == 0 ) num /= 2 ; // While num is divisible by 3, divide it by 3 while (num % 3 == 0 ) num /= 3 ; // If num got reduced to 1 then it has // only 2 and 3 as prime factors if (num == 1 ) count++; } return count; } // Driver code public static void main (String[] args) { int l = 1 , r = 10 ; System.out.println (findTwoThreePrime(l, r)); } //This code is contributed by ajit } |
Python3
# Python3 program to count the numbers # within a range whose prime factors # are only 2 and 3 # Function to count the number within # a range whose prime factors are only # 2 and 3 def findTwoThreePrime(l, r) : # Start with 2 so that 1 # doesn't get counted if (l = = 1 ) : l + = 1 count = 0 for i in range (l, r + 1 ) : num = i # While num is divisible by 2, # divide it by 2 while (num % 2 = = 0 ) : num / / = 2 ; # While num is divisible by 3, # divide it by 3 while (num % 3 = = 0 ) : num / / = 3 # If num got reduced to 1 then it has # only 2 and 3 as prime factors if (num = = 1 ) : count + = 1 return count # Driver code if __name__ = = "__main__" : l = 1 r = 10 print (findTwoThreePrime(l, r)) # This code is contributed by Ryuga |
C#
// C# program to count the numbers // within a range whose prime factors // are only 2 and 3 using System; class GFG { // Function to count the number // within a range whose prime // factors are only 2 and 3 static int findTwoThreePrime( int l, int r) { // Start with 2 so that 1 // doesn't get counted if (l == 1) l++; int count = 0; for ( int i = l; i <= r; i++) { int num = i; // While num is divisible by 2, // divide it by 2 while (num % 2 == 0) num /= 2; // While num is divisible by 3, // divide it by 3 while (num % 3 == 0) num /= 3; // If num got reduced to 1 then it // has only 2 and 3 as prime factors if (num == 1) count++; } return count; } // Driver code static public void Main () { int l = 1, r = 10; Console.WriteLine(findTwoThreePrime(l, r)); } } // This code is contributed by akt_mit |
PHP
<?php // PHP program to count the numbers // within a range whose prime factors // are only 2 and 3 // Function to count the number // within a range whose prime // factors are only 2 and 3 function findTwoThreePrime( $l , $r ) { // Start with 2 so that 1 // doesn't get counted if ( $l == 1) $l ++; $count = 0; for ( $i = $l ; $i <= $r ; $i ++) { $num = $i ; // While num is divisible by 2, // divide it by 2 while ( $num % 2 == 0) $num /= 2; // While num is divisible by 3, // divide it by 3 while ( $num % 3 == 0) $num /= 3; // If num got reduced to 1 then it has // only 2 and 3 as prime factors if ( $num == 1) $count ++; } return $count ; } // Driver code $l = 1; $r = 10; echo findTwoThreePrime( $l , $r ); // This code is contributed by ajit ?> |
Javascript
<script> // Javascript program to count the numbers // within a range whose prime factors // are only 2 and 3 // Function to count the number // within a range whose prime // factors are only 2 and 3 function findTwoThreePrime(l, r) { // Start with 2 so that 1 // doesn't get counted if (l == 1) l++; let count = 0; for (let i = l; i <= r; i++) { let num = i; // While num is divisible by 2, // divide it by 2 while (num % 2 == 0) num = parseInt(num / 2, 10); // While num is divisible by 3, // divide it by 3 while (num % 3 == 0) num = parseInt(num / 3, 10); // If num got reduced to 1 then it // has only 2 and 3 as prime factors if (num == 1) count++; } return count; } let l = 1, r = 10; document.write(findTwoThreePrime(l, r)); </script> |
Time Complexity: O((r-l)*log2(r-l))
Auxiliary Space: O(1), since no extra space has been taken.
Contact Us