Given a positive integer N, the task is to count the number of integers from the range [1, N] having exactly 5 divisors.
Examples:
Input: N = 18
Output: 1
Explanation:
From all the integers over the range [1, 18], 16 is the only integer that has exactly 5 divisors, i.e. 1, 2, 8, 4 and 16.
Therefore, the count of such integers is 1.Input: N = 100
Output: 2
Naive Approach: The simplest approach to solve the given problem is to iterate over the range [1, N] and count those integers in this range having the count of divisors as 5.
C++
// C++ code for the approach#include <iostream>#include <cmath>using namespace std;void SieveOfEratosthenes(int n, bool prime[], bool primesquare[], int a[]) { //For more details check out: https://www.neveropen.co.uk/sieve-of-eratosthenes/ // Create a boolean array "prime[0..n]" and // initialize all entries it as true. A value // in prime[i] will finally be false if i is // Not a prime, else true. for (int i = 2; i <= n; i++) prime[i] = true; // Create a boolean array "primesquare[0..n*n+1]" // and initialize all entries it as false. A value // in squareprime[i] will finally be true if i is // square of prime, else false. for (int i = 0; i <= (n * n + 1); i++) primesquare[i] = false; // 1 is not a prime number prime[1] = false; 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 starting from p * p for (int i = p * p; i <= n; i += p) prime[i] = false; } } int j = 0; for (int p = 2; p <= n; p++) { if (prime[p]) { // Storing primes in an array a[j] = p; // Update value in primesquare[p*p], // if p is prime. primesquare[p * p] = true; j++; } }} // Function to count divisorsint countDivisors(int n) { // If number is 1, then it will have only 1 // as a factor. So, total factors will be 1. if (n == 1) return 1; bool prime[n + 1], primesquare[n * n + 1]; int a[n]; // for storing primes upto n // Calling SieveOfEratosthenes to store prime // factors of n and to store square of prime // factors of n SieveOfEratosthenes(n, prime, primesquare, a); // ans will contain total number of distinct // divisors int ans = 1; // Loop for counting factors of n for (int i = 0;; i++) { // a[i] is not less than cube root n if (a[i] * a[i] * a[i] > n) break; // Calculating power of a[i] in n. int cnt = 1; // cnt is power of prime a[i] in n. while (n % a[i] == 0) // if a[i] is a factor of n { n = n / a[i]; cnt = cnt + 1; // incrementing power } // Calculating the number of divisors // If n = a^p * b^q then total divisors of n // are (p+1)*(q+1) ans = ans * cnt; } // if a[i] is greater than cube root of n // First case if (prime[n]) ans = ans * 2; // Second case else if (primesquare[n]) ans = ans * 3; // Third case else if (n != 1) ans = ans * 4; return ans; // Total divisors}// Function to count the number of integers with exactly 5 divisorsint countIntegers(int n) { // Store count of numbers with exactly 5 divisors int count = 0; // loop from 1 to n to check its distinct count of divisors for (int i = 1; i <= n; i++) { // Function Call int divisors = countDivisors(i); // If the number of divisors is 5, check if it is a prime square if (divisors == 5 ) { count++; } } return count;}// Driver codeint main() { int n = 100; cout << countIntegers(n) << endl; return 0;} |
Java
// Java code for the approachimport java.util.Vector;public class GFG { static void SieveOfEratosthenes(int n, boolean prime[], boolean primesquare[], int a[]) { // Create a boolean array "prime[0..n]" and // initialize all entries it as true. A value // in prime[i] will finally be false if i is // Not a prime, else true. for (int i = 2; i <= n; i++) prime[i] = true; /* Create a boolean array "primesquare[0..n*n+1]" and initialize all entries it as false. A value in squareprime[i] will finally be true if i is square of prime, else false.*/ for (int i = 0; i < ((n * n) + 1); i++) primesquare[i] = false; // 1 is not a prime number prime[1] = false; 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 * 2; i <= n; i += p) prime[i] = false; } } int j = 0; for (int p = 2; p <= n; p++) { if (prime[p]) { // Storing primes in an array a[j] = p; // Update value in // primesquare[p*p], // if p is prime. primesquare[p * p] = true; j++; } } } // Function to count divisors static int countDivisors(int n) { // If number is 1, then it will // have only 1 as a factor. So, // total factors will be 1. if (n == 1) return 1; boolean prime[] = new boolean[n + 1]; boolean primesquare[] = new boolean[(n * n) + 1]; // for storing primes upto n int a[] = new int[n]; // Calling SieveOfEratosthenes to // store prime factors of n and to // store square of prime factors of n SieveOfEratosthenes(n, prime, primesquare, a); // ans will contain total number // of distinct divisors int ans = 1; // Loop for counting factors of n for (int i = 0;; i++) { // a[i] is not less than cube root n if (a[i] * a[i] * a[i] > n) break; // Calculating power of a[i] in n. // cnt is power of prime a[i] in n. int cnt = 1; // if a[i] is a factor of n while (n % a[i] == 0) { n = n / a[i]; // incrementing power cnt = cnt + 1; } // Calculating the number of divisors // If n = a^p * b^q then total // divisors of n are (p+1)*(q+1) ans = ans * cnt; } // if a[i] is greater than cube root // of n // First case if (prime[n]) ans = ans * 2; // Second case else if (primesquare[n]) ans = ans * 3; // Third case else if (n != 1) ans = ans * 4; return ans; // Total divisors } // Function to count the number of integers with exactly // 5 divisors static int countIntegers(int n) { // Store count of numbers with exactly 5 divisors int count = 0; // loop from 1 to n to check its distinct count of // divisors for (int i = 1; i <= n; i++) { // Function Call int divisors = countDivisors(i); // If the number of divisors is 5, check if it // is a prime square if (divisors == 5) { count++; } } return count; } // Driver code public static void main(String[] args) { int N = 100; System.out.println(countIntegers(N)); }} |
Python3
# Python3 code for the approachimport mathdef sieveOfEratosthenes(n): # Create a boolean array "prime[0..n]" and initialize # all entries it as true. A value in prime[i] will # finally be false if i is Not a prime, else true. prime = [True for i in range(n+1)] p = 2 while(p * p <= n): # 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 p += 1 # Store prime numbers primes = [] for p in range(2, n+1): if prime[p]: primes.append(p) return primes # Function to count divisorsdef countDivisors(n, primes): # If number is 1, then it will have only 1 as a factor. # So, total factors will be 1. if (n == 1): return 1 ans = 1 # Loop for counting factors of n i = 0 while (primes[i] <= math.sqrt(n)): # a[i] is not less than square root of n cnt = 1 # cnt is power of prime a[i] in n. while (n % primes[i] == 0): # if a[i] is a factor of n n = n // primes[i] cnt += 1 # incrementing power ans = ans * cnt # Calculating the number of divisors i += 1 # if a[i] is greater than square root of n if (n > 1): ans = ans * 2 return ans # Total divisors # Function to count the number of integers with exactly 5 divisorsdef countIntegers(n): # Store count of numbers with exactly 5 divisors count = 0 # Get all prime numbers up to n primes = sieveOfEratosthenes(n) # loop from 1 to n to check its distinct count of divisors for i in range(1, n+1): # Function Call divisors = countDivisors(i, primes) # If the number of divisors is 5, check if it is a prime square if (divisors == 5 and int(math.sqrt(i))**2 == i): count += 1 return count # Driver codeif __name__ == "__main__": # Input integer n = 100 # Function call print(countIntegers(n)) |
Javascript
function sieveOfEratosthenes(n){ // Create a boolean array "prime[0..n]" and initialize // all entries it as true. A value in prime[i] will // finally be false if i is Not a prime, else true. let prime = new Array(n+1).fill(true); let p = 2; while(p * p <= n) { // 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; } } p += 1; } // Store prime numbers let primes = []; for (let p = 2; p <= n; p++) { if (prime[p] == true) { primes.push(p); } } return primes;}// Function to count divisorsfunction countDivisors(n, primes) { // If number is 1, then it will have only 1 as a factor. // So, total factors will be 1. if (n == 1) { return 1; } let ans = 1; // Loop for counting factors of n let i = 0; while (primes[i] <= Math.sqrt(n)) { // a[i] is not less than square root of n let cnt = 1; // cnt is power of prime a[i] in n. while (n % primes[i] == 0) { // if a[i] is a factor of n n = n / primes[i]; cnt += 1; // incrementing power } ans = ans * cnt; // Calculating the number of divisors i += 1; } // if a[i] is greater than square root of n if (n > 1) { ans = ans * 2; } return ans; // Total divisors}// Function to count the number of integers with exactly 5 divisorsfunction countIntegers(n) { // Store count of numbers with exactly 5 divisors let count = 0; // Get all prime numbers up to n let primes = sieveOfEratosthenes(n); // loop from 1 to n to check its distinct count of divisors for (let i = 1; i <= n; i++) { // Function Call let divisors = countDivisors(i, primes); // If the number of divisors is 5, check if it is a prime square if (divisors == 5 && Math.sqrt(i)**2 == i) { count += 1; } } return count;}// Driver codelet n = 100;console.log(countIntegers(n)); |
Output
2
Time Complexity: O(N4/3)
Auxiliary Space: O(1)
Efficient Approach: The above approach can also be optimized by observing a fact that the numbers that have exactly 5 divisors can be expressed in the form of p4, where p is a prime number as the count of divisors is exactly 5. Follow the below steps to solve the problem:
- Generate all primes such that their fourth power is less than 1018 by using Sieve of Eratosthenes and store it in vector, say A[].
- Initialize two variables, say low as 0 and high as A.size() – 1.
- For performing the Binary Search iterate until low is less than high and perform the following steps:
- Find the value of mid as the (low + high)/2.
- Find the value of fourth power of element at indices mid (mid – 1) and store it in a variable, say current and previous respectively.
- If the value of current is N, then print the value of A[mid] as the result.
- If the value of current is greater than N and previous is at most N, then print the value of A[mid] as the result.
- If the value of current is greater than N then update the value of high as (mid – 1). Otherwise, update the value of low as (mid + 1).
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>#define ll long long intconst int MAX = 1e5;using namespace std;// Function to calculate the value of// (x^y) using binary exponentiationll power(ll x, unsigned ll y){ // Stores the value of x^y ll res = 1; // Base Case if (x == 0) return 0; while (y > 0) { // If y is odd multiply // x with result if (y & 1) res = (res * x); // Otherwise, divide y by 2 y = y >> 1; x = (x * x); } return res;}// Function to perform the Sieve Of// Eratosthenes to find the prime// number over the range [1, 10^5]void SieveOfEratosthenes( vector<pair<ll, ll> >& v){ bool prime[MAX + 1]; memset(prime, true, sizeof(prime)); prime[1] = false; for (int p = 2; p * p <= MAX; p++) { // If prime[p] is not changed // then it is a prime if (prime[p] == true) { // Set all the multiples of // p to non-prime for (int i = p * 2; i <= MAX; i += p) prime[i] = false; } } int num = 1; // Iterate over the range [1, MAX] for (int i = 1; i <= MAX; i++) { // Store all the prime number if (prime[i]) { v.push_back({ i, num }); num++; } }}// Function to find the primes having// only 5 divisorsint countIntegers(ll n){ // Base Case if (n < 16) { return 0; } // First value of the pair has the // prime number and the second value // has the count of primes till that // prime numbers vector<pair<ll, ll> > v; // Precomputing all the primes SieveOfEratosthenes(v); int low = 0; int high = v.size() - 1; // Perform the Binary search while (low <= high) { int mid = (low + high) / 2; // Calculate the fourth power of // the curr and prev ll curr = power(v[mid].first, 4); ll prev = power(v[mid - 1].first, 4); if (curr == n) { // Return value of mid return v[mid].second; } else if (curr > n and prev <= n) { // Return value of mid-1 return v[mid - 1].second; } else if (curr > n) { // Update the value of high high = mid - 1; } else { // Update the value of low low = mid + 1; } } return 0;}// Driver Codeint main(){ ll N = 100; cout << countIntegers(N); return 0;} |
Java
// Java program for the above approachimport java.util.Vector;public class GFG { static int MAX = (int)1e5; public static class pair { long first; long second; pair(long first, long second) { this.first = first; this.second = second; } } // Function to calculate the value of // (x^y) using binary exponentiation static long power(long x, long y) { // Stores the value of x^y long res = 1; // Base Case if (x == 0) return 0; while (y > 0) { // If y is odd multiply // x with result if ((y & 1) == 1) res = (res * x); // Otherwise, divide y by 2 y = y >> 1; x = (x * x); } return res; } // Function to perform the Sieve Of // Eratosthenes to find the prime // number over the range [1, 10^5] static void SieveOfEratosthenes(Vector<pair> v) { boolean prime[] = new boolean[MAX + 1]; for (int i = 0; i < prime.length; i++) { prime[i] = true; } prime[1] = false; for (int p = 2; p * p <= MAX; p++) { // If prime[p] is not changed // then it is a prime if (prime[p] == true) { // Set all the multiples of // p to non-prime for (int i = p * 2; i <= MAX; i += p) prime[i] = false; } } int num = 1; // Iterate over the range [1, MAX] for (int i = 1; i <= MAX; i++) { // Store all the prime number if (prime[i]) { v.add(new pair(i, num)); num++; } } } // Function to find the primes having // only 5 divisors static long countIntegers(long n) { // Base Case if (n < 16) { return 0; } // First value of the pair has the // prime number and the second value // has the count of primes till that // prime numbers Vector<pair> v = new Vector<>(); // Precomputing all the primes SieveOfEratosthenes(v); int low = 0; int high = v.size() - 1; // Perform the Binary search while (low <= high) { int mid = (low + high) / 2; // Calculate the fourth power of // the curr and prev long curr = power(v.get(mid).first, 4); long prev = power(v.get(mid - 1).first, 4); if (curr == n) { // Return value of mid return v.get(mid).second; } else if (curr > n && prev <= n) { // Return value of mid-1 return v.get(mid - 1).second; } else if (curr > n) { // Update the value of high high = mid - 1; } else { // Update the value of low low = mid + 1; } } return 0; } // Driver code public static void main(String[] args) { long N = 100; System.out.println(countIntegers(N)); }}// This code is contributed by abhinavjain194 |
Python3
# Python program for the above approach# Function to calculate the value of# (x**y) using binary exponentiationdef power(x, y): # Stores the value of x**y res = 1 # Base Case if x == 0: return 0 while y > 0: # If y is odd multiply # x with result if y&1: res = (res*x) # otherwise, divide y by 2 y = y >> 1 x = (x*x) return res# Function to perform the Sieve of# Eratosthenes to find the prime# number over the range [1, 10^5]def sieveofeartoshenes(vec): prime = [] for i in range(pow(10, 5)+1): prime.append(True) prime[1] = False p = 2 while (p * p <= pow(10, 5)): # If prime[p] is not # changed, then it is a prime if (prime[p] == True): # Updating all multiples of # to non-prime for i in range(p * p, pow(10, 5) + 1, p): prime[i] = False p += 1 num = 1 # Iterate over the range [1, pow(10, 5)] for i in range(1, pow(10, 5)+1): # Stores all the prime number if prime[i]: vec.append([i, num]) num += 1def count_integer(n): # Base Case if n < 16: return 0 # First value of the pair has the # prime number and the second value # has the cont of primes till that # prime numbers vec = [[]] # precomputing all the primes sieveofeartoshenes(vec) low = 0 high = len(vec)-1 # perform the Binary Search while low <= high: mid = (low+high)//2 # Calculate the fourth power of # the curr and prev curr = power(vec[mid][0], 4) prev = power(vec[mid-1][0], 4) if curr == n: # Return value of mid return vec[mid][1] elif curr > n and prev <= n: # Return value of mid-1 return vec[mid-1][1] elif curr > n: # Update the value of low high = mid - 1 else: # Update the value of high low = mid + 1n = 100ans = count_integer(n)print(ans)# This code is contributed by Aditya Sharma |
C#
// C# code to implement the approachusing System;using System.Collections.Generic;public class pair { public long first; public long second; public pair(long first, long second) { this.first = first; this.second = second; }}class GFG { static int MAX = (int)1e5; // Function to calculate the value of // (x^y) using binary exponentiation static long power(long x, long y) { // Stores the value of x^y long res = 1; // Base Case if (x == 0) return 0; while (y > 0) { // If y is odd multiply // x with result if ((y & 1) == 1) res = (res * x); // Otherwise, divide y by 2 y = y >> 1; x = (x * x); } return res; } // Function to perform the Sieve Of // Eratosthenes to find the prime // number over the range [1, 10^5] static void SieveOfEratosthenes(List<pair> v) { bool[] prime = new bool[MAX + 1]; for (int i = 0; i < prime.Length; i++) { prime[i] = true; } prime[1] = false; for (int p = 2; p * p <= MAX; p++) { // If prime[p] is not changed // then it is a prime if (prime[p] == true) { // Set all the multiples of // p to non-prime for (int i = p * 2; i <= MAX; i += p) prime[i] = false; } } int num = 1; // Iterate over the range [1, MAX] for (int i = 1; i <= MAX; i++) { // Store all the prime number if (prime[i]) { v.Add(new pair(i, num)); num++; } } } // Function to find the primes having // only 5 divisors static long countIntegers(long n) { // Base Case if (n < 16) { return 0; } // First value of the pair has the // prime number and the second value // has the count of primes till that // prime numbers List<pair> v = new List<pair>(); // Precomputing all the primes SieveOfEratosthenes(v); int low = 0; int high = v.Count - 1; // Perform the Binary search while (low <= high) { int mid = (low + high) / 2; // Calculate the fourth power of // the curr and prev long curr = power(v[mid].first, 4); long prev = power(v[mid - 1].first, 4); if (curr == n) { // Return value of mid return v[mid].second; } else if (curr > n && prev <= n) { // Return value of mid-1 return v[mid - 1].second; } else if (curr > n) { // Update the value of high high = mid - 1; } else { // Update the value of low low = mid + 1; } } return 0; } // Driver code public static void Main(string[] args) { long N = 100; Console.WriteLine(countIntegers(N)); }}// This code is contributed by phasing17 |
Javascript
// JavaScript program for the above approach// Function to calculate the value of// (x**y) using binary exponentiationfunction power(x, y){ // Stores the value of x**y let res = 1; // Base Case if (x === 0) { return 0; } while (y > 0) { // If y is odd multiply // x with result if (y&1) { res = (res*x); } // otherwise, divide y by 2 y = y >> 1; x = (x*x); } return res;}// Function to perform the Sieve of// Eratosthenes to find the prime// number over the range [1, 10^5]function sieveofeartoshenes(vec) { let prime = []; for (let i = 0; i <= Math.pow(10, 5)+1; i++) { prime.push(true); } prime[1] = false; let p = 2; while (p * p <= Math.pow(10, 5)) { // If prime[p] is not // changed, then it is a prime if (prime[p] === true) { // Updating all multiples of // to non-prime for (let i = p * p; i <= Math.pow(10, 5) + 1; i += p) { prime[i] = false; } } p += 1; } let num = 1; // Iterate over the range [1, pow(10, 5)] for (let i = 1; i <= Math.pow(10, 5)+1; i++) { // Stores all the prime number if (prime[i]) { vec.push([i, num]); num += 1; } }}function count_integer(n) { // Base Case if (n < 16) { return 0; } // First value of the pair has the // prime number and the second value // has the cont of primes till that // prime numbers let vec = [[]]; // precomputing all the primes sieveofeartoshenes(vec); let low = 0; let high = vec.length-1; // perform the Binary Search while (low <= high) { let mid = (low+high)//2; // Calculate the fourth power of // the curr and prev let curr = power(vec[mid][0], 4); let prev = power(vec[mid-1][0], 4); if (curr === n) { // Return value of mid return vec[mid][1]; } else if (curr > n && prev <= n) { // Return value of mid-1 return vec[mid-1][1]; } else if (curr > n) { // Update the value of low high = mid - 1; } else { // Update the value of high low = mid + 1 } }}let n = 100let ans = count_integer(n)console.log(ans)// This code is contributed by phasing17 |
Output:
2
Time Complexity: O(N*log N)
Auxiliary Space: O(N)
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!
