Given a positive integer N, the task is to find the Nth smallest number in the sequence which is having exactly 4 divisors.
Examples:
Input: 4
Output: 14
Explanation: The numbers in the sequence that has 4 divisors are 6, 8, 10, 14, …, the fourth number in the sequence is 14.Input: 24
Output: 94
Approach: This problem can be solved by observing that the number i having a prime factorization of p1a1 * p2a2 * p3a3…pkak, then the number of divisors of i is (a1+1)(a2+1)…(ak+1). So for i to have exactly 4 divisors, it should be equal to the product of two distinct primes or some prime number raised to the power 3. Follow the steps below to solve the problem:
- Initialize arrays divs[] and vis[] to store the number of divisors of any number and to check if given number is considered or not respectively.
- Initialize a variable cnt as 0 to store number of elements having exactly 4 divisors.
- Now, use the sieve of Eratosthenes algorithm.
- Iterate while cnt is less than n, using a variable i start from 2:
- If i is prime:
- Iterate in the range [2*i, 1000000] using the variable j with increment of i:
- If the number j is already considered, then continue.
- Update vis[j] as true and initialize variables currNum as j and count as 0.
- Divide the currNum by i while currNum % i is equal to 0, increment div[j] and count by 1.
- If currNum is equal to 1, count is equal to 3 and divs[j] is equal to 3, then increment cnt by 1.
- Otherwise, if currNum is not equal to 1, count is equal to 1, divs[j] is equal to 1 and divs[currNum] is equal to 0, then increment cnt by 1.
- If cnt is equal to N, then print j and return.
- Iterate in the range [2*i, 1000000] using the variable j with increment of i:
- If i is prime:
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 the nth number which// has exactly 4 divisorsint nthNumber(int n){ // The divs[] array to store number of // divisors of every element int divs[1000000]; // The vis[] array to check if given number // is considered or not bool vis[1000000]; // The cnt stores number of elements having // exactly 4 divisors int cnt = 0; // Iterate while cnt less than n for (int i = 2; cnt < n; i++) { // If i is a prime if (divs[i] == 0) { // Iterate in the range [2*i, 1000000] with // increment of i for (int j = 2 * i; j < 1000000; j += i) { // If the number j is already considered if (vis[j]) { continue; } vis[j] = 1; int currNum = j; int count = 0; // Dividing currNum by i until currNum % i is // equal to 0 while (currNum % i == 0) { divs[j]++; currNum = currNum / i; count++; } // Case a single prime in its factorization if (currNum == 1 && count == 3 && divs[j] == 3) { cnt++; } else if (currNum != 1 && divs[currNum] == 0 && count == 1 && divs[j] == 1) { // Case of two distinct primes which // divides j exactly once each cnt++; } if (cnt == n) { return j; } } } } return -1;}// Driver Codeint main(){ // Given Input int N = 24; // Function Call cout << nthNumber(N) << endl; return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG { // Function to find the nth number which // has exactly 4 divisors static int nthNumber(int n) { // The divs[] array to store number of // divisors of every element int divs[] = new int[1000000]; // The vis[] array to check if given number // is considered or not boolean vis[] = new boolean[1000000]; // The cnt stores number of elements having // exactly 4 divisors int cnt = 0; // Iterate while cnt less than n for (int i = 2; cnt < n; i++) { // If i is a prime if (divs[i] == 0) { // Iterate in the range [2*i, 1000000] with // increment of i for (int j = 2 * i; j < 1000000; j += i) { // If the number j is already considered if (vis[j]) { continue; } vis[j] = true; int currNum = j; int count = 0; // Dividing currNum by i until currNum % // i is equal to 0 while (currNum % i == 0) { divs[j]++; currNum = currNum / i; count++; } // Case a single prime in its // factorization if (currNum == 1 && count == 3 && divs[j] == 3) { cnt++; } else if (currNum != 1 && divs[currNum] == 0 && count == 1 && divs[j] == 1) { // Case of two distinct primes which // divides j exactly once each cnt++; } if (cnt == n) { return j; } } } } return -1; } // Driver Code public static void main(String[] args) { // Given Input int N = 24; // Function Call System.out.println(nthNumber(N)); }}// This code is contributed by Potta Lokesh |
Python3
# Python program for the above approach# Function to find the nth number which# has exactly 4 divisorsdef nthNumber(n): # The divs[] array to store number of # divisors of every element divs = [0 for i in range(1000000)]; # The vis[] array to check if given number # is considered or not vis = [0 for i in range(1000000)]; # The cnt stores number of elements having # exactly 4 divisors cnt = 0; # Iterate while cnt less than n for i in range(2, n): # If i is a prime if (divs[i] == 0): # Iterate in the range [2*i, 1000000] with # increment of i for j in range(2 * i, 1000000): # If the number j is already considered if (vis[j]): continue; vis[j] = 1; currNum = j; count = 0; # Dividing currNum by i until currNum % i is # equal to 0 while (currNum % i == 0): divs[j] += 1; currNum = currNum // i; count += 1; # Case a single prime in its factorization if (currNum == 1 and count == 3 and divs[j] == 3): cnt += 1 elif (currNum != 1 and divs[currNum] == 0 and count == 1 and divs[j] == 1): # Case of two distinct primes which # divides j exactly once each cnt += 1 if (cnt == n): return j; return -1;# Driver Code# Given InputN = 24;# Function Callprint(nthNumber(N));# This code is contributed by gfgking. |
C#
// C# program for the above approachusing System;// Function to find minimum number of// elements required to obtain sum Kclass GFG{// Function to find the nth number which// has exactly 4 divisorsstatic int nthNumber(int n){ // The divs[] array to store number of // divisors of every element int[] divs = new int[1000000]; // The vis[] array to check if given number // is considered or not int[] vis = new int[1000000]; // The cnt stores number of elements having // exactly 4 divisors int cnt = 0; // Iterate while cnt less than n for(int i = 2; cnt < n; i++) { // If i is a prime if (divs[i] == 0) { // Iterate in the range [2*i, 1000000] with // increment of i for(int j = 2 * i; j < 1000000; j += i) { // If the number j is already considered if (vis[j] != 0) { continue; } vis[j] = 1; int currNum = j; int count = 0; // Dividing currNum by i until currNum % i is // equal to 0 while (currNum % i == 0) { divs[j]++; currNum = currNum / i; count++; } // Case a single prime in its factorization if (currNum == 1 && count == 3 && divs[j] == 3) { cnt++; } else if (currNum != 1 && divs[currNum] == 0 && count == 1 && divs[j] == 1) { // Case of two distinct primes which // divides j exactly once each cnt++; } if (cnt == n) { return j; } } } } return -1;}// Driver Codestatic public void Main (){ // Given Input int N = 24; // Function Call Console.Write(nthNumber(N));}}// This code is contributed by sanjoy_62 |
Javascript
<script>// JavaScript program for the above approach// Function to find the nth number which// has exactly 4 divisorsfunction nthNumber(n){ // The divs[] array to store number of // divisors of every element let divs = new Array(1000000); for(var i = 0; i < divs.length; i++) { divs[i] = 0; } // The vis[] array to check if given number // is considered or not let vis = new Array(1000000); for(var i = 0; i < vis.length; i++) { vis[i] = 0; } // The cnt stores number of elements having // exactly 4 divisors let cnt = 0; // Iterate while cnt less than n for(let i = 2; cnt < n; i++) { // If i is a prime if (divs[i] == 0) { // Iterate in the range [2*i, 1000000] with // increment of i for(let j = 2 * i; j < 1000000; j += i) { // If the number j is already considered if (vis[j]) { continue; } vis[j] = true; let currNum = j; let count = 0; // Dividing currNum by i until currNum % // i is equal to 0 while (currNum % i == 0) { divs[j]++; currNum = Math.floor(currNum / i); count++; } // Case a single prime in its // factorization if (currNum == 1 && count == 3 && divs[j] == 3) { cnt++; } else if (currNum != 1 && divs[currNum] == 0 && count == 1 && divs[j] == 1) { // Case of two distinct primes which // divides j exactly once each cnt++; } if (cnt == n) { return j; } } } } return -1;}// Driver Code// Given Inputlet N = 24;// Function Calldocument.write(nthNumber(N));// This code is contributed by code_hunt</script> |
Output
94
Time Complexity: O(Nlog(log(N))), where N is 1000000.
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!
