Find Nth smallest number having exactly 4 divisors in Java
In this tutorial, we are going to find Nth smallest number having exactly 4 divisors in Java. The challenge is to find the Nth smallest number in the order of numbers with exactly 4 divisors provided an integer with a positive value N. Let’s see a few examples to understand it. In the input, the number N will be given to us.
Example 1:
Input: N = 6
Output: 21
Explanation: The numbers like 6, 8, 10, 14,15, and so on are the ones in the sequence list with exactly having four divisors therefore the sixth number in that list is 21. We know that there are exactly four ways to divide the number 21, with the divisors 1, 3, 7, and 21.
Example 2:
Input: N = 14
Output: 39
Explanation: The numbers 6, 8, 10, 14,15, 21, and so on are the ones in the sequence list with exactly having four divisors therefore the sixth number in that list having exactly 4 divisors is 39. We know that there are exactly four ways to divide the number 39, and the divisors are 1, 3, 13, and 39
Note: Exact four-factor numbers are always of the type p^3 or pq, where p and q are (different) primes; that is, they are either semiprime, or the product of two distinct primes, or the cubes of a prime number. We may support this by listing each item in the following order: p3: 1, p, p2; p3 p * q: 1, p, q, pq (presuming, without losing generality, that q > p).
Approach: Using Brute Force
The approach is straightforward. With this brute force approach we find the Nth smallest number with having exactly 4 divisors by iterating through numbers starting from2 and verify whether each number has exactly 4 divisors or not. Since prime integers raised to the power of three have exactly four divisors, if it is prime, it also confirms if its cube root is prime. It uses a divisor counting method to count the divisors if the number is not prime. Until the Nth integer with precisely 4 divisors is obtained, this process is repeated.
FileName: NthSmallestWithExact4Divs.java
import java.io.*;
public class NthSmallestWithExact4Divs {
// function to check if a given input number is prime or not
public static boolean isAPrimeNumb(int n) {
if (n <= 1) {
return false;
}
for (int i = 2; i <= Math.sqrt(n); i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
// Method to get the nth smallest number which has exactly 4 divisors
static int isExactFourDivs(int n) {
int noOfcnt = 0;
// Iterate the numbers until getting the nth number with having exactly 4 divisors
for (int num = 2; noOfcnt < n; num++) {
int tCnt = 0;
// verify whether it is a prime number or not
if (isAPrimeNumb(num)) {
if (isAPrimeNumb((int)Math.cbrt(num))) { //Verify that the number's cube root is prime.
tCnt = 4; // There are precisely four divisors for a prime integer raised to the power of 3.
}
} else {
// Use a counting divisors method to determine how many divisors there are.
for (int i = 1; i <= Math.sqrt(num); i++) {
if (num % i == 0) {
if (num / i == i) { // There should only be one count if both factors are equal.
tCnt++;
} else { // if not, count both factors
tCnt += 2;
}
}
}
if (tCnt == 4) {
noOfcnt++;
}
}
// Return the number n if we have identified the one with exactly four divisors.
if (noOfcnt == n) {
return num;
}
}
return -1;
}
public static void main(String[] args) {
int n = 14; // provide Nth number as input
int m = 12;
System.out.println("The " + n +" th with exactly 4 divisors is : " +isExactFourDivs(n));
System.out.println("The " + m +" th with exactly 4 divisors is : " +isExactFourDivs(m));
}
}
Output:
The 14 th with exactly 4 divisors is: 39
The 12 th with exactly 4 divisors is: 35
Complexity Analysis: The program iterates until it finds the Nth number with 4 divisors, iterating N times. It checks if the number is prime, it takes time complexity of O(sqrt(num),). If not prime, it counts divisors using a divisor counting method, it takes time complexity of O(sqrt(num),). The overall time complexity can be is O(N * sqrt(num), where N is the input number and num is the current number. The space complexity is O(1) because it maintains constant space for variables and functions calls.
If N is big or has a lot of divisors, the brute-force method might not work well. Finding the Nth lowest number with exactly 4 divisors can be done more quickly and efficiently with the use of optimised algorithms such as prime factorization or sieving techniques.
Approach : Using Prime Factorization
The solution to this problem is to note that if the integer i has a prime factorization of p1^a1 * p2^a2 * p3^a3 … pk^ak, then (a1+1) (a2+1) … (ak+1) is the number of divisors of i. Therefore, it must equal the product of two different primes or some prime integer raised to the power of three in order for i to have exactly four divisors. To solve the issue, use the following measures:
Step 1: Set up the arrays called divArr[] and visArr[] to hold the number of divisors of each given number and, accordingly, to determine whether or not a given number is taken into consideration.
Step 2: Set the value of the variable called noOfcnt to 0 in order to record the number of elements that have precisely 4 divisors.
Step 3: Implement the Basic Approach to check the number is prime or not accordingly.
Step 4: Repeat using a variable I start from 2 and continue until noOfcnt is smaller than n:
4.1: If the integer i is prime:
4.1.1: Use the variable j and an increment of i to iterate across the range [2*i, 1000000]:
4.1.1.1: If the number j has already been considered, then continue.
4.2: Update visArr[j] to true and set variables currNumb and onOfcnt to j and 0 respectively.
4.2.1: While currNumb % i is equal to 0, divide the currNumb by i. Then, increment divArr[j] and totalCnt by 1.
4.3: In case currNumb equals 1, totalCnt equals 3, and divArr[j] equals 3, then noOfcnt should be increased by 1.
4.4: Otherwise, increase noOfcnt by 1 if currNum is not equal to 1, totalCnt is equal to 1, divArr [j] is equal to 1, and divArr[currNumb] is equal to 0.
4.5: Print j and return if the constant variable noOfcnt equals N.
FileName: NthSmallestWithExact4Divs
import java.io.*;
class NthSmallestWithExact4Divs {
// function to check if a given input number is prime or not
public static boolean isAPrimeNumb(int n) {
if (n <= 1) {
return false;
}
for (int i = 2; i <= Math.sqrt(n); i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
// Method to find the nth number which has exactly 4 divisors
static int isExactFourDivs(int n) {
int[] divArr = new int[1000000];
boolean[] visArr = new boolean[1000000];
int noOfcnt = 0;
for (int i = 2; noOfcnt < n; i++) {
if (isAPrimeNumb (i)) { // Check if i is prime
for (int j = 2 * i; j < 1000000; j += i) {
if (visArr[j]) {
continue;
}
visArr[j] = true;
int currNumb = j;
int totalCnt = 0;
while (currNumb % i == 0) {
divArr[j]++;
currNumb = currNumb / i;
totalCnt++;
}
if (currNumb == 1 && totalCnt == 3 && divArr[j] == 3) {
noOfcnt++;
} else if (currNumb != 1 && divArr[currNumb] == 0 && totalCnt == 1 && divArr[j] == 1) {
noOfcnt++;
}
if (noOfcnt == n) {
return j;
}
}
}
}
return -1;
}
public static void main(String[] args) {
int n = 24;
System.out.println(isExactFourDivs(n));
}
}
Output:
94
Complexity Analysis: The above program uses the isAPrimeNumb() function as it iterates up to the square root of a given number to check prime or not, with a time complexity of O(sqrt(n)) The outer loop iterates until count called noOfcnt equals to n, while the nested loop iterates over multiples of primes up to 10^5, resulting in an overall time complexity of O(n * (n/2)) = O(n^2).
The space complexity is O(1) because the code employs two arrays for divisor counts and visited numbers during prime factorization, each with a size of 10^5, resulting in an auxiliary space complexity of O(1).