Powerful Number in Java
We will define a powerful number in this article and write Java programs to determine whether a given number is a powerful number or not. Java coding interviews and academic exams usually involve questions about the powerful number program.
Powerful Number
A number X is referred to as the powerful number if all of its prime divisors and the square of those prime numbers must leave the number X with a zero remainder when divided.
In other words, the factor of the number X must equal the square of all the prime factors of the number X. The form of X must also be l2m3, where l and m are positive integers.
If the following conditions hold for every value of P that is a factor of X: X = l2m3, l > 0, m > 0, X% P = 0, and X% (P * P) = 0, and P is a prime number, then we can claim that X is a powerful number.
If p2 divides a given number n for every prime number p, that number is said to be powerful. For instance, 36 is a powerful number. It is divided by 3 and the square of 3 (i.e., 9).
The initial group of powerful numbers includes:
1, 4, 8, 9, 16, 25, 27, 32, 36, 49, 64 . . . . .
Our objective is to determine whether a given number n is powerful or not.
How to Find the powerful Numbers
Step 1: Assign a number to the variable.
Step 2: Determine the prime factors of the given variable.
Step 3. Store factors in a List.
Step 4: Find the square of the factors in the list as you iterate over them.
Step 5: Determine whether or not each factor in the list has a square that divides the supplied number.
The given number is not a powerful number if the square of any one factor does not divide it.
A number is a powerful number if the prime factor and the square of the prime factor divide the provided number.
Powerful Number Examples
Example 1:
Let us take, X = 15
Factors of X: 3, 5 (prime factors)
Square the prime factors, we get 3 * 3 = 9, and 5 * 5 = 25.
Now, we divide 15 by 9 and 25, respectively.
15 % 9 = 6, and 15 % 25 = 15. Thus, we see remainder is not zero. Hence, the number 15 is not a powerful number.
Example 2:
Let us take, X = 27
Factors of X: 3 (prime factors)
Square of prime factors, we get 3 * 3 = 9.
Divide 27 by 9 we get:
27 % 9 = 0. Thus, we see remainder is zero in every case. Also, 27 can be written as 33, where 3 > 0. Hence, the number 27 is a powerful number.
Example 3:
Let us take, X = 100
Factors of X: 2, 5 (prime factors)
Square of prime factors, we get 2 * 2 = 4 and 5 * 5 = 25.
Now, we divide 100 by 4 and 25, respectively.
100 % 4 = 0, and 100 % 25 = 0. Thus, we see remainder is zero. Hence, the number 100 is a powerful number.
Note: A prime number can never become a powerful number, as the prime factor of the number is the number itself, and the square of the number can never divide the number itself.
Example 4:
Let us take X=5. 5 is a prime number. Hence, its prime factor is also 5. Also, 5 * 5 = 25. Now, 5 % 25 = 5, which is not 0. Hence, 5 is not a powerful number.
Example 5:
Let us take X=7. 7 is a prime number. Hence, its prime factor is also 7. Also, 7 * 7 = 49. Now, 7 % 49 = 7, which is not 0. Hence, 7 is not a powerful number.
Program to find Powerful Number
File name: Pow.java
// Java program to find if a number is powerful or not.
import java.io.* ;
import java.util.* ;
class Pow {
// function to
//determine whether a number is powerful or not
static boolean isPowerful(int p)
{
// First, divide the number.
//by two repeatedly.
while (p % 2 == 0) {
int power = 0 ;
while (p % 2 == 0) {
p /= 2;
power++ ;
}
// Return false if only 2^1 divides n (no higher powers).
if (power == 1)
return false ;
}
// This loop will run if n is not a power of 2.
// re-do the previous steps.
for (int factor = 3; factor <= Math.sqrt(p); factor += 2) {
// Determine the greatest power of the "factor" that divides n.
int power = 0;
while (p % factor == 0) {
p = p / factor;
power++;
}
// Return false if only factor^1 divides n (not higher powers).
if (power == 1)
return false;
}
// Now, if n is not a prime number, it must equal 1.
// We return false if n is not 1 because prime numbers are not powerful numbers.
return (p == 1);
}
// code logic
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
if (isPowerful(n))
System.out.print("YES\n");
else
System.out.print("NO\n");
}
}Output 1:
In the above-displayed output, 20 is the given number, and as 20 is not divided by its prime factor's square, 20 is not a powerful number.
Therefore, the program prints “NO”.
Output 2:
In the above-displayed output, 27 is the given number, and as 27 is divided by its prime factor's square, 27 is a powerful number. The prime factor of 27 is 3, the square of 3 is 9, and 9 divides 27.
Therefore, the program prints “YES”.
Output 3:
In the above-displayed output, 5 is the given number, and 5 is not divided by its prime factor's square, so 5 is not a powerful number. The prime factor of 5 is 5 itself, the square of 5 is 25, and 25 doesn’t divide 5.
Therefore, the program prints “NO”.
Program to display powerful and not powerful numbers
File name: Pow1.java
// Java program to display powerful numbers and not powerful numbers.
import java.io.* ;
import java.util.* ;
class Pow1 {
// function to determine whether a number is powerful or not
static boolean isPowerful(int p)
{
// First, divide the number
// by two repeatedly.
while (p % 2 == 0) {
int power = 0 ;
while (p % 2 == 0) {
p /= 2 ;
power++ ;
}
// Return false if only 2^1 divides n (no higher powers)
if (power == 1)
return false ;
}
// This loop will run if n is not a power of 2.
// re-do the previous steps.
for (int factor = 3; factor <= Math.sqrt(p); factor += 2) {
// Determine the greatest power of the "factor" that divides n.
int power = 0 ;
while (p % factor == 0) {
p = p / factor ;
power++ ;
}
// Return false if only factor^1 divides n (not higher powers)
if (power == 1)
return false ;
}
// Now, if n is not a prime number, it must equal 1.
// We return false if n is not 1 because prime numbers are not powerful
// numbers.
return (p == 1) ;
}
// code logic
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in) ;
int n=sc.nextInt() ;
for(int i=1;i<=n;i++){
if (isPowerful(i))
System.out.print(i+" is a powerful number\n") ;
else
System.out.print(i+" is not a powerful number\n") ;
}
}
}Output 1:
In the above-displayed output, a range of powerful numbers is displayed. Here, the input is 10, and the program prints the powerful numbers and not powerful numbers from 1 to 10.
The powerful numbers from 1 to 10 are 1, 4, 8, and 9.
Output 2:
In the above-displayed output, a range of powerful numbers is displayed. Here, the input is 20, and the program prints the powerful numbers and not powerful numbers from 1 to 20.
The powerful numbers from 1 to 10 are 1, 4, 8, 9, and 16.
Program to find powerful numbers in a given range
File name: Pow2.java
// Java program to find only the powerful numbers.
import java.io.* ;
import java.util.* ;
class Pow2 {
// function to
//determine whether a number is powerful or not
static boolean isPowerful(int p)
{
// First, divide the number
//by two repeatedly.
while (p % 2 == 0) {
int power = 0;
while (p % 2 == 0) {
p /= 2;
power++ ;
}
// Return false if only 2^1 divides n (no higher powers)
if (power == 1)
return false ;
}
// This loop will run if n is not a power of 2.
// re-do the previous steps.
for (int factor = 3; factor <= Math.sqrt(p); factor += 2) {
// Determine the greatest power of the "factor" that divides n.
int power = 0;
while (p % factor == 0) {
p = p / factor;
power++ ;
}
// Return false if only factor^1 divides n (not higher powers)
if (power == 1)
return false ;
}
// Now, if n is not a prime number, it must equal 1.
// We return false if n is not 1 because prime numbers are not powerful
// numbers.
return (p == 1) ;
}
// code logic
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in) ;
int n=sc.nextInt();
System.out.print("Powerful numbers : ") ;
for(int i=1;i<=n;i++){
if (isPowerful(i))
System.out.print(i+" ") ;
}
}Output:
The above-displayed output displays a range of powerful numbers from 1 to 27.