Given an integer N, find the number of natural numbers less than or equal to N and have 4 factors.
Example:
Input: N = 8
Output: 2
Explanation: {1} is divisor set of 1
{1, 2} is divisor set of 2
{1, 3} is divisor set of 3
{1, 2, 4} is divisor set of 4
{1, 5} is divisor set of 5
{1, 2, 3, 6} is divisor set of 6
{1, 7} is divisor set of 7
{1, 2, 4, 8} is divisor set of 8
So, 6 and 8 are only natural numbers less than or equal to N and count of divisors 4.Input: N = 2
Output: 0
Naive Approach:
The naive approach for the problem is that we can traverse from 1 to N and count number of divisors of each one of them. If the count comes out to be 4 , then increase the resultant number say res by 1. Finally at the end of traversal we will be having the number of natural numbers less than or equal to N and have 4 factors in the variable res.
We will be counting divisors efficiently using the approach of complexity O(n1/3) as mentioned and discussed in this article: Count Divisors of n in O(n^1/3).
Algorithm:
- Define a function SieveOfEratosthenes that accepts n, a boolean array prime[], a boolean array primesquare[], and an integer array a[] as parameters.
- Initialize all entries in prime[] as true and all entries in primesquare[] as false.
- Mark prime[1] as false.
- Use the Sieve of Eratosthenes algorithm to mark all non-prime numbers in the range 2 to n in the prime[] array.
- Store all prime numbers in the range 2 to n in the integer array a[].
- For each prime number p in the integer array a[], update the primesquare[p*p] to true.
- Define a function countDivisors that accepts an integer n as a parameter.
- If n is 1, return 1 as it will have only 1 as a factor.
- Declare a boolean array prime[] and primesquare[] of size n+1 and n*n+1 respectively.
- Declare an integer array a[] of size n.
- Call the SieveOfEratosthenes function with parameters n, prime[], primesquare[], and a[].
- Initialize a variable ans to 1 that will contain the total number of distinct divisors.
- Loop through all prime numbers a[i] in the integer array a[] until a[i]^3 > n.
- Calculate the power of a[i] in n using a while loop, incrementing the power for each iteration until n is no longer divisible by a[i].
- Multiply ans by (cnt+1) where cnt is the power of a[i] in n.
- If n is greater than 1 after the loop, then it has a prime factor greater than cube root of n, which will have a power of 1. Multiply ans by 2 in this case.
- If n is a square of a prime number, multiply ans by 3.
- If n is not equal to 1 after the above cases, it means n has two distinct prime factors. Multiply ans by 4 in this case.
- Return ans.
- Define the main function.
- Initialize an integer N to the maximum range.
- Initialize an integer variable res to 0 that will store the result.
- Loop through each number from 1 to N.
- If the count of divisors of the current number is 4, increment res by 1.
- Print the value of res as the result.
Below is the implementation of the approach:
C++
// C++ code for the approach#include <bits/stdc++.h>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}// Driver codeint main() { // Input int N = 8; // resultant counter int res = 0; // traversing through each number from 1 to N for(int i = 1; i <= N; i++) { // if count of divisors is 4 // increase res by 1 if( countDivisors(i) == 4) res += 1; } // Print res cout<< res << endl; return 0;} |
Java
import java.util.Arrays;class Solution { static boolean[] prime; static boolean[] primesquare; public static int[] sieveOfEratosthenes(int n) { // Initialize a boolean array to mark prime numbers prime = new boolean[n + 1]; Arrays.fill(prime, true); // Initialize a boolean array to mark square prime // numbers primesquare = new boolean[(n * n) + 1]; Arrays.fill(primesquare, false); // Initialize an array to store prime numbers int[] a = new int[n]; // 1 is not a prime number prime[1] = false; // Find prime numbers using the Sieve of // Eratosthenes algorithm int p = 2; while (p * p <= n) { if (prime[p]) { for (int i = p * p; i <= n; i += p) { prime[i] = false; // Mark multiples of prime // numbers as non-prime } } p++; } // Store prime numbers in the array int j = 0; for (p = 2; p <= n; p++) { if (prime[p]) { a[j] = p; primesquare[p * p] = true; // Mark square prime numbers j++; } } return a; } public static int countDivisors(int n) { if (n == 1) { return 1; } // Get prime numbers and related information int[] a = sieveOfEratosthenes(n); int ans = 1; int i = 0; // Count divisors using the prime factorization of // the number while (true) { if (a[i] * a[i] * a[i] > n) { break; } int cnt = 1; while (n % a[i] == 0) { n = n / a[i]; cnt++; } ans *= cnt; i++; } // Handle remaining factors if (n > 1) { if (prime[n]) { ans *= 2; } else if (primesquare[n]) { ans *= 3; } else { ans *= 4; } } return ans; // Return the total number of divisors } public static void main(String[] args) { int N = 8; int res = 0; // Count the number of numbers with exactly four // divisors for (int i = 1; i <= N; i++) { if (countDivisors(i) == 4) { res++; } } System.out.println(res); // Print the result }} |
Python3
# Function to find prime numbers using the Sieve of Eratosthenes algorithmdef SieveOfEratosthenes(n): prime = [True] * (n + 1) # Initialize a boolean array to mark prime numbers primesquare = [False] * ((n * n) + 1) # Initialize a boolean array to mark square prime numbers a = [0] * n # Initialize an array to store prime numbers prime[1] = False # 1 is not a prime number p = 2 while p * p <= n: if prime[p]: for i in range(p * p, n + 1, p): prime[i] = False # Mark multiples of prime numbers as non-prime p += 1 j = 0 for p in range(2, n + 1): if prime[p]: a[j] = p # Store prime numbers in the array primesquare[p * p] = True # Mark square prime numbers j += 1 return a, prime, primesquare # Return the arrays of prime numbers and related information# Function to count divisors of a numberdef countDivisors(n): if n == 1: return 1 a, prime, primesquare = SieveOfEratosthenes(n) # Get prime numbers and related information ans = 1 i = 0 while True: if a[i] * a[i] * a[i] > n: break cnt = 1 while n % a[i] == 0: n = n // a[i] cnt += 1 ans *= cnt i += 1 if prime[n]: ans *= 2 elif primesquare[n]: ans *= 3 elif n != 1: ans *= 4 return ans # Return the total number of divisors# Driver codedef main(): N = 8 res = 0 for i in range(1, N + 1): if countDivisors(i) == 4: res += 1 print(res) # Print the resultif __name__ == "__main__": main() # Call the main function if the script is executed directly |
C#
using System;class GFG{ static bool[] prime; static bool[] primesquare; public static int[] SieveOfEratosthenes(int n) { // Initialize a boolean array to mark prime numbers prime = new bool[n + 1]; Array.Fill(prime, true); // Initialize a boolean array to mark square prime numbers primesquare = new bool[(n * n) + 1]; Array.Fill(primesquare, false); // Initialize an array to store prime numbers int[] a = new int[n]; // 1 is not a prime number prime[1] = false; // Find prime numbers using the Sieve of Eratosthenes algorithm int p = 2; while (p * p <= n) { if (prime[p]) { for (int i = p * p; i <= n; i += p) { prime[i] = false; // Mark multiples of prime numbers as non-prime } } p++; } // Store prime numbers in the array int j = 0; for (p = 2; p <= n; p++) { if (prime[p]) { a[j] = p; primesquare[p * p] = true; // Mark square prime numbers j++; } } return a; } public static int CountDivisors(int n) { if (n == 1) { return 1; } // Get prime numbers and related information int[] a = SieveOfEratosthenes(n); int ans = 1; int i = 0; // Count divisors using the prime factorization of the number while (true) { if (a[i] * a[i] * a[i] > n) { break; } int cnt = 1; while (n % a[i] == 0) { n = n / a[i]; cnt++; } ans *= cnt; i++; } // Handle remaining factors if (n > 1) { if (prime[n]) { ans *= 2; } else if (primesquare[n]) { ans *= 3; } else { ans *= 4; } } return ans; // Return the total number of divisors } public static void Main() { int N = 8; int res = 0; // Count the number of numbers with exactly four divisors for (int i = 1; i <= N; i++) { if (CountDivisors(i) == 4) { res++; } } Console.WriteLine(res); // Print the result }} |
Output
2
Time Complexity: O(N * N1/3) as for loop which is running contributes O(N) and inside it countDivisors function contributes N1/3 time. So, overall time complexity becomes O(N * N1/3). Here, N is the input integer.
Auxiliary Space: O(N) as arrays like prime and primesquare has been created. Here, N is the input integer.
Approach: The idea to solve the problem is based on the following observation:
- Any number M can be written in form M = p1e1 * p2e2 * . . . where (p1, p2 . . .) are primes and (e1, e2 . . .) are respective exponents.
- The total number of factors of M is therefore (e + 1)*(e + 1)* . . .
- From above points, for the count of divisors of a natural number to be 4, there are two cases:-
- Case-1: N = p1 * p2 (where p1 and p2 are two distinct prime numbers)
- Case-2: N = p3 (where p is a prime number)
- So there must be two primes whose multiplication is less than N or one prime whose cube is less than N.
Follow the steps mentioned below to solve the problem:
- Find all the prime numbers less than or equal to N using the sieve of Eratosthenes.
- For Case-1 iterate through all prime numbers and use binary search to find a number of primes whose product is at most N.
- For Case-2, do a binary search to find the number of primes whose cube is less than or equal to N.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find primes <= Nvector<int> SieveOfEratosthenes(int 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. bool prime[n + 1]; memset(prime, true, sizeof(prime)); for (long long 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 greater than or // equal to the square of it for (long long int i = p * p; i <= n; i += p) prime[i] = false; } } // Vector for storing prime number // less than or equal to N vector<int> primes; // Store all prime numbers for (int p = 2; p <= n; p++) if (prime[p]) primes.push_back(p); return primes;}// Find floor of cube root of Nint primeCubic(vector<int>& primes, int N){ // Val stores cube root of N long long int l = 0, r = N, mid, val; // Binary search loop for finding // floor of cube root of N while (l <= r) { mid = (l + r) / 2; if ((mid * mid * mid) <= N) { val = mid; l = mid + 1; } else { r = mid - 1; } } // Iterator for finding index with // value just greater than Val in primes auto it = upper_bound(primes.begin(), primes.end(), val); it--; return (it - primes.begin() + 1);}// Function to find primes with product <= Nint primeProduct(vector<int>& primes, int N){ // Stores the answer int answer = 0; // Iterator storing pointer to // current prime auto cur = primes.begin(); // Loop for traversing all primes // Find number of indices less than // current indices for which product // is less than or equal to N for (auto i : primes) { long long int add = upper_bound(primes.begin(), cur, (N / i)) - primes.begin(); answer += add; cur++; } return answer;}// Function to find the total countint print(int N){ vector<int> primes = SieveOfEratosthenes(N); int answer = 0; answer += primeCubic(primes, N); answer += primeProduct(primes, N); return answer;}// Driver codeint main(){ int N = 8; // Print function Call cout << print(N); return 0;} |
Java
// Java program for above approachimport java.util.*;public class Solution{ // Function to find primes <= N static ArrayList<Integer> SieveOfEratosthenes(int 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. boolean[] prime = new boolean[n + 1]; Arrays.fill(prime, 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 greater than or // equal to the square of it for (int i = p * p; i <= n; i += p) prime[i] = false; } } // Vector for storing prime number // less than or equal to N ArrayList<Integer> primes = new ArrayList<>(); // Store all prime numbers for (int p = 2; p <= n; p++) if (prime[p]) primes.add(p); return primes; } static int upper_bound(ArrayList<Integer> arr, int lo, int hi, int key) { int mid, N = arr.size(); // Initialise starting index and // ending index int low = lo; int high = hi; // Till low is less than high while (low < high && low != N) { mid = low + (high - low) / 2; // If key is greater than or equal // to arr[mid], then find in // right subarray if (key >= arr.get(mid)) { low = mid + 1; } // If key is less than arr[mid] // then find in left subarray else { high = mid; } } return low; } // Find floor of cube root of N static int primeCubic(ArrayList<Integer> primes, int N) { // Val stores cube root of N int l = 0, r = N, mid, val = 0; // Binary search loop for finding // floor of cube root of N while (l <= r) { mid = (l + r) / 2; if ((mid * mid * mid) <= N) { val = mid; l = mid + 1; } else { r = mid - 1; } } // Iterator for finding index with // value just greater than Val in primes int it = upper_bound(primes, 0, primes.size(), val); it--; return (it + 1); } // Function to find primes with product <= N static int primeProduct(ArrayList<Integer> primes, int N) { // Stores the answer int answer = 0; // Iterator storing pointer to // current prime int cur = 0; // Loop for traversing all primes // Find number of indices less than // current indices for which product // is less than or equal to N for (int i : primes) { int add = upper_bound(primes, 0, cur, (N / i)); answer += add; cur++; } return answer; } // Function to find the total count static int print(int N) { ArrayList<Integer> primes = SieveOfEratosthenes(N); int answer = 0; answer += primeCubic(primes, N); answer += primeProduct(primes, N); return answer; } // Driver code public static void main(String[] args) { int N = 8; // Print function Call System.out.println(print(N)); }}// This code is contributed by karandeep1234. |
Python3
# Python3 program for the above approachimport bisect# Function to find primes <= Ndef 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] * (n + 1) for p in range(2, 1 + int(n ** 0.5)): # If prime[p] is not changed, # then it is a prime if (prime[p] == True): # Update all multiples # of p greater than or # equal to the square of it for i in range(p * p, n + 1, p): prime[i] = False # Vector for storing prime number # less than or equal to N primes = [] # Store all prime numbers for p in range(2, n + 1): if prime[p]: primes.append(p) return primes# Find floor of cube root of Ndef primeCubic(primes, N): #Val stores cube root of N l = 0 r = N # Binary search loop for finding # floor of cube root of N while (l <= r): mid = (l + r) // 2 if ((mid * mid * mid) <= N): val = mid l = mid + 1 else: r = mid - 1 # Iterator for finding index with # value just greater than Val in primes it = bisect.bisect_right(primes, val) return it# Function to find primes with product <= Ndef primeProduct(primes, N): # Stores the answer answer = 0 # Iterator storing pointer to # current prime cur = 0 # Loop for traversing all primes # Find number of indices less than # current indices for which product # is less than or equal to N for i in primes: add = bisect.bisect_right(primes[:cur], N // i) answer += add cur += 1 return answer# Function to find the total countdef print_(N): primes = SieveOfEratosthenes(N) answer = 0 answer += primeCubic(primes, N) answer += primeProduct(primes, N) return answer# Driver codeN = 8# Print function Callprint(print_(N))# This code is contributed by phasing17 |
C#
using System;using System.Collections.Generic;class GFG{ // Function to find primes <= N static int[] SieveOfEratosthenes(int 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. 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 greater than or // equal to the square of it for (int i = p * p; i <= n; i += p) prime[i] = false; } } // Array for storing prime number // less than or equal to N // int []primes= new int[]; List<int> primes = new List<int>(); // Store all prime numbers for (int p = 2; p <= n; p++) if (prime[p]) primes.Add(p); return primes.ToArray(); } static int upper_bound(int[] arr, int N, int X) { int mid; int low = 0; int high = N; while (low < high) { mid = low + (high - low) / 2; if (X >= arr[mid]) low = mid + 1; else high = mid; } if (low < N && arr[low] <= X) low++; return low; } // Find floor of cube root of N static int primeCubic(int[] primes, int N) { // Val stores cube root of N int l = 0, r = N, mid, val = 0; // Binary search loop for finding // floor of cube root of N while (l <= r) { mid = (l + r) / 2; if ((mid * mid * mid) <= N) { val = mid; l = mid + 1; } else { r = mid - 1; } } // Iterator for finding index with // value just greater than Val in primes int it = upper_bound(primes, primes.Length, val); return it; } // Function to find primes with product <= N static int primeProduct(int[] primes, int N) { // Stores the answer int answer = 0; // Iterator storing pointer to // current prime int cur = 0; // Loop for traversing all primes // Find number of indices less than // current indices for which product // is less than or equal to N for (int i = 0; i < primes.Length; i++) { int add = upper_bound(primes, cur, (N / primes[i])); answer += add; cur++; } return answer; } // Function to find the total count static int print(int N) { int[] primes = SieveOfEratosthenes(N); int answer = 0; answer += primeCubic(primes, N); answer += primeProduct(primes, N); return answer; } static void Main() { int N = 8; // Print function Call Console.Write(print(N)); }}// This code is contributed by garg28harsh. |
Javascript
// Function to find primes <=Nconst 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 = Array(n + 1).fill(true); for (let p = 2; p * p <= n; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p]) { // Update all multiples // of p greater than or // equal to the square of it for (let i = p * p; i <= n; i += p) prime[i] = false; } } // Vector for storing prime number// less than or equal to N let primes = []; // Store all prime numbers for (let p = 2; p <= n; p++) if (prime[p]) primes.push(p); return primes;}const upper_bound = (arr, lo, hi, key) => { let mid, N = arr.length; // Initialise starting index and// ending index let low = lo; let high = hi; // Till low is less than high while (low < high && low != N) { mid = low + Math.floor((high - low) / 2); // If key is greater than or equal // to arr[mid], then find in // right subarray if (key >= arr[mid]) { low = mid + 1; } // If key is less than arr[mid] // then find in left subarray else { high = mid; } } return low;}// Find floor of cube root of Nconst primeCubic = (primes, N) => { // Val stores cube root of N let l = 0, r = N, mid, val = 0; // Binary search loop for finding // floor of cube root of N while (l <= r) { mid = Math.floor((l + r) / 2); if ((mid * mid * mid) <= N) { val = mid; l = mid + 1; } else { r = mid - 1; } } // Iterator for finding index with // value just greater than Val in primes let it = upper_bound(primes, 0, primes.length, val); it--; return (it + 1);} // Function to find primes with product <= Nconst primeProduct = (primes, N) => { let answer = 0; // Iterator storing pointer to // current prime let cur = 0; // Loop for traversing all primes // Find number of indices less than // current indices for which product // is less than or equal to N for (let i of primes) { let add = upper_bound(primes, 0, cur, Math.floor(N / i)); answer += add; cur++; } return answer;}// Function to find the total countconst print = (N) => { let primes = SieveOfEratosthenes(N); let answer = 0; answer += primeCubic(primes, N); answer += primeProduct(primes, N); return answer;}console.log(print(8));// This code is contributed by anskalyan3. |
Output
2
Time Complexity: O(N * log(logN) + N + logN) ≈ O(N * log (logN))
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!
