# Powerful Number

The given problem is to identify and print "Powerful Numbers" within a given range from 1 to a specified size. A powerful number is a positive integer that can be represented as the power of two or the product of distinct prime numbers (each raised to the power of 1). For example, 4, 8, 9, 16, 36, and 81 are powerful numbers since they can be represented as 2^2, 2^3, 3^2, 2^4, 2^2 * 3^2, and 3^4, respectively.

## Explanation

The code provided is a C program that identifies and prints powerful numbers within a given range. Let's go through the code step-by-step:

1. The function `is_poweful(int num)` checks whether a given number `num` is a powerful number or not. It does this by finding the factors and their powers in the number. If the number is divisible by 2, it divides it by 2 and increments the `power` variable until the number is no longer divisible by 2. If the power of 2 is 1, it means the number is not powerful, and the function returns 0. Then, in the loop that runs from 3 to the square root of the number, it finds the other factors (odd prime factors) and their respective powers. If any power is 1, the function returns 0; otherwise, it returns the number itself if it's a powerful number.

2. The function `print_poweful_no(int size)` takes a parameter `size`, which represents the upper limit of the range. It iterates through the numbers from 1 to `size` and uses the `is_poweful()` function to check if each number is powerful. If a number is found to be powerful, it is printed. The function also keeps track of the count of powerful numbers and prints the total count at the end.

3. In the `main()` function, a test case is performed where the function `print_poweful_no(1000)` is called to find and print powerful numbers from 1 to 1000.

## Pseudocode

``````Function is_powerful(num):
power = 0
factor = 0
if num is divisible by 2:
while num is divisible by 2:
num = num / 2
power = power + 1
if power is 1:
return false
for factor = 3 to square root of num, incrementing by 2:
power = 0
while num is divisible by factor:
num = num / factor
power = power + 1
if power is 1:
return false
return num

Function print_powerful_numbers(size):
if size <= 0:
return
counter = 0
for i = 1 to size:
if is_powerful(i) is true:
counter = counter + 1
print i
if counter is divisible by 6:
print new line
print total count of powerful numbers

Main:
Call print_powerful_numbers(1000)
``````

## Code Solution

Here given code implementation process.

``````// C program
// Powerful Number
#include <stdio.h>
#include <math.h>

//Check whether given number is powerful number or not
int is_poweful(int num)
{
// Define loop control variables
int power = 0;
int factor = 0;
if (num % 2 == 0)
{
// When number is divisible by 2 so we reduce number and
// Finding its power
while (num % 2 == 0)
{
num = num / 2;
power++;
}
if (power == 1)
{
// When In case calculated numbers are only one power (2^1)
// So that is not powerful number
return 0;
}
}
//Executing the loop under square root of number
for (factor = 3; factor <= sqrt(num); factor += 2)
{
//reset power
power = 0;
//Calculate factor power
while (num % factor == 0)
{
num = num / factor;
power++;
}
if (power == 1)
{
//When factor power is one
return 0;
}
}
//If calculated resulting number is 1 , so we get powerful number
return num;
}
//Display powerful numbers from 1 to given size
void print_poweful_no(int size)
{
if (size <= 0)
{
return;
}
int counter = 0;
printf("\n\tPowerful Number from (1 to %d)\n", size);
//Display powerful number form 1 to given size
for (int i = 1; i <= size; ++i)
{
if (is_poweful(i) == 1)
{
counter++;
//Display poweful number
printf("\t%d", i);
if (counter % 6 == 0)
{
printf("\n");
}
}
}
printf("\n\t---------------------\n");
printf("\t Total : %d\n", counter);
}
int main()
{
//Test case
print_poweful_no(1000);
return 0;
}
// Note when you are use gcc compiler in linux,
// Then compile your program like this
// Compile : gcc test.c -o test -lm
// Run : ./test
// Here test.c is program file, and test is executable``````

#### Output

``````	Powerful Number from (1 to 1000)
1	4	8	9	16	25
27	32	36	49	64	72
81	100	108	121	125	128
144	169	196	200	216	225
243	256	288	289	324	343
361	392	400	432	441	484
500	512	529	576	625	648
675	676	729	784	800	841
864	900	961	968	972	1000

---------------------
Total : 54``````
``````// Java program
// Powerful Number
class PowefulNo
{
//Check whether given number is powerful number or not
public int is_poweful(int num)
{
// Define loop control variables
int power = 0;
int factor = 0;
if (num % 2 == 0)
{
// When number is divisible by 2 so we reduce number and
// Finding its power
while (num % 2 == 0)
{
num = num / 2;
power++;
}
if (power == 1)
{
// When In case calculated numbers are only one power (2^1)
// So that is not powerful number
return 0;
}
}
//Executing the loop under square root of number
for (factor = 3; factor <= Math.sqrt(num); factor += 2)
{
//reset power
power = 0;
//Calculate factor power
while (num % factor == 0)
{
num = num / factor;
power++;
}
if (power == 1)
{
//When factor power is one
return 0;
}
}
//If calculated resulting number is 1 , so we get powerful number
return num;
}
//Display powerful numbers from 1 to given size
public void print_poweful_no(int size)
{
if (size <= 0)
{
return;
}
int counter = 0;
System.out.print("\n\tPowerful Number from (1 to " + size + ")\n");
//Display powerful number form 1 to given size
for (int i = 1; i <= size; ++i)
{
if (is_poweful(i) == 1)
{
counter++;
//Display poweful number
System.out.print("\t" + i + "");
if (counter % 6 == 0)
{
System.out.print("\n");
}
}
}
System.out.print("\n\t---------------------\n");
System.out.print("\t Total : " + counter + "\n");
}
public static void main(String[] args)
{
PowefulNo obj = new PowefulNo();
int size = 1000;
obj.print_poweful_no(size);
}
}``````

#### Output

``````	Powerful Number from (1 to 1000)
1	4	8	9	16	25
27	32	36	49	64	72
81	100	108	121	125	128
144	169	196	200	216	225
243	256	288	289	324	343
361	392	400	432	441	484
500	512	529	576	625	648
675	676	729	784	800	841
864	900	961	968	972	1000

---------------------
Total : 54``````
``````//Include header file
#include <iostream>
#include <math.h>
using namespace std;

// C++ program
// Powerful Number

class PowefulNo
{
public:
//Check whether given number is powerful number or not
int is_poweful(int num)
{
// Define loop control variables
int power = 0;
int factor = 0;
if (num % 2 == 0)
{
// When number is divisible by 2 so we reduce number and
// Finding its power
while (num % 2 == 0)
{
num = num / 2;
power++;
}
if (power == 1)
{
// When In case calculated numbers are only one power (2^1)
// So that is not powerful number
return 0;
}
}
//Executing the loop under square root of number
for (factor = 3; factor <= sqrt(num); factor += 2)
{
//reset power
power = 0;
//Calculate factor power
while (num % factor == 0)
{
num = num / factor;
power++;
}
if (power == 1)
{
//When factor power is one
return 0;
}
}
//If calculated resulting number is 1 , so we get powerful number
return num;
}
//Display powerful numbers from 1 to given size
void print_poweful_no(int size)
{
if (size <= 0)
{
return;
}
int counter = 0;
cout << "\n\tPowerful Number from (1 to " << size << ")\n";
//Display powerful number form 1 to given size
for (int i = 1; i <= size; ++i)
{
if (this->is_poweful(i) == 1)
{
counter++;
//Display poweful number
cout << "\t" << i << "";
if (counter % 6 == 0)
{
cout << "\n";
}
}
}
cout << "\n\t---------------------\n";
cout << "\t Total : " << counter << "\n";
}
};
int main()
{
PowefulNo obj = PowefulNo();
int size = 1000;
obj.print_poweful_no(size);
return 0;
}``````

#### Output

``````	Powerful Number from (1 to 1000)
1	4	8	9	16	25
27	32	36	49	64	72
81	100	108	121	125	128
144	169	196	200	216	225
243	256	288	289	324	343
361	392	400	432	441	484
500	512	529	576	625	648
675	676	729	784	800	841
864	900	961	968	972	1000

---------------------
Total : 54``````
``````//Include namespace system
using System;
// C# program
// Powerful Number
class PowefulNo
{
//Check whether given number is powerful number or not
public int is_poweful(int num)
{
// Define loop control variables
int power = 0;
int factor = 0;
if (num % 2 == 0)
{
// When number is divisible by 2 so we reduce number and
// Finding its power
while (num % 2 == 0)
{
num = num / 2;
power++;
}
if (power == 1)
{
// When In case calculated numbers are only one power (2^1)
// So that is not powerful number
return 0;
}
}
//Executing the loop under square root of number
for (factor = 3; factor <= Math.Sqrt(num); factor += 2)
{
//reset power
power = 0;
//Calculate factor power
while (num % factor == 0)
{
num = num / factor;
power++;
}
if (power == 1)
{
//When factor power is one
return 0;
}
}
//If calculated resulting number is 1 , so we get powerful number
return num;
}
//Display powerful numbers from 1 to given size
public void print_poweful_no(int size)
{
if (size <= 0)
{
return;
}
int counter = 0;
Console.Write("\n\tPowerful Number from (1 to " + size + ")\n");
//Display powerful number form 1 to given size
for (int i = 1; i <= size; ++i)
{
if (is_poweful(i) == 1)
{
counter++;
//Display poweful number
Console.Write("\t" + i);
if (counter % 6 == 0)
{
Console.Write("\n");
}
}
}
Console.Write("\n\t---------------------\n");
Console.Write("\t Total : " + counter + "\n");
}
public static void Main(String[] args)
{
PowefulNo obj = new PowefulNo();
int size = 1000;
obj.print_poweful_no(size);
}
}``````

#### Output

``````	Powerful Number from (1 to 1000)
1	4	8	9	16	25
27	32	36	49	64	72
81	100	108	121	125	128
144	169	196	200	216	225
243	256	288	289	324	343
361	392	400	432	441	484
500	512	529	576	625	648
675	676	729	784	800	841
864	900	961	968	972	1000

---------------------
Total : 54``````
``````<?php
// Php program
// Powerful Number
class PowefulNo
{
//Check whether given number is powerful number or not
public	function is_poweful(\$num)
{
// Define loop control variables
\$power = 0;
\$factor = 0;
if (\$num % 2 == 0)
{
// When number is divisible by 2 so we reduce number and
// Finding its power
while (\$num % 2 == 0)
{
\$num = intval(\$num / 2);
\$power++;
}
if (\$power == 1)
{
// When In case calculated numbers are only one power (2^1)
// So that is not powerful number
return 0;
}
}
//Executing the loop under square root of number
for (\$factor = 3; \$factor <= sqrt(\$num); \$factor += 2)
{
//reset power
\$power = 0;
//Calculate factor power
while (\$num % \$factor == 0)
{
\$num = intval(\$num / \$factor);
\$power++;
}
if (\$power == 1)
{
//When factor power is one
return 0;
}
}
//If calculated resulting number is 1 , so we get powerful number
return \$num;
}
//Display powerful numbers from 1 to given size
public	function print_poweful_no(\$size)
{
if (\$size <= 0)
{
return;
}
\$counter = 0;
echo "\n\tPowerful Number from (1 to ". \$size .")\n";
//Display powerful number form 1 to given size
for (\$i = 1; \$i <= \$size; ++\$i)
{
if (\$this->is_poweful(\$i) == 1)
{
\$counter++;
//Display poweful number
echo "\t". \$i;
if (\$counter % 6 == 0)
{
echo "\n";
}
}
}
echo "\n\t---------------------\n";
echo "\t Total : ". \$counter ."\n";
}
}

function main()
{
\$obj = new PowefulNo();
\$size = 1000;
\$obj->print_poweful_no(\$size);
}
main();``````

#### Output

``````	Powerful Number from (1 to 1000)
1	4	8	9	16	25
27	32	36	49	64	72
81	100	108	121	125	128
144	169	196	200	216	225
243	256	288	289	324	343
361	392	400	432	441	484
500	512	529	576	625	648
675	676	729	784	800	841
864	900	961	968	972	1000

---------------------
Total : 54``````
``````// Node Js program
// Powerful Number
class PowefulNo
{
//Check whether given number is powerful number or not
is_poweful(num)
{
// Define loop control variables
var power = 0;
var factor = 0;
if (num % 2 == 0)
{
// When number is divisible by 2 so we reduce number and
// Finding its power
while (num % 2 == 0)
{
num = parseInt(num / 2);
power++;
}
if (power == 1)
{
// When In case calculated numbers are only one power (2^1)
// So that is not powerful number
return 0;
}
}
//Executing the loop under square root of number
for (factor = 3; factor <= Math.sqrt(num); factor += 2)
{
//reset power
power = 0;
//Calculate factor power
while (num % factor == 0)
{
num = parseInt(num / factor);
power++;
}
if (power == 1)
{
//When factor power is one
return 0;
}
}
//If calculated resulting number is 1 , so we get powerful number
return num;
}
//Display powerful numbers from 1 to given size
print_poweful_no(size)
{
if (size <= 0)
{
return;
}
var counter = 0;
process.stdout.write("\n\tPowerful Number from (1 to " + size + ")\n");
//Display powerful number form 1 to given size
for (var i = 1; i <= size; ++i)
{
if (this.is_poweful(i) == 1)
{
counter++;
//Display poweful number
process.stdout.write("\t" + i);
if (counter % 6 == 0)
{
process.stdout.write("\n");
}
}
}
process.stdout.write("\n\t---------------------\n");
process.stdout.write("\t Total : " + counter + "\n");
}
}

function main()
{
var obj = new PowefulNo();
var size = 1000;
obj.print_poweful_no(size);
}
main();``````

#### Output

``````	Powerful Number from (1 to 1000)
1	4	8	9	16	25
27	32	36	49	64	72
81	100	108	121	125	128
144	169	196	200	216	225
243	256	288	289	324	343
361	392	400	432	441	484
500	512	529	576	625	648
675	676	729	784	800	841
864	900	961	968	972	1000

---------------------
Total : 54``````
``````import math
#  Python 3 program
#  Powerful Number
class PowefulNo :
# Check whether given number is powerful number or not
def is_poweful(self, num) :
#  Define loop control variables
power = 0
factor = 0
if (num % 2 == 0) :
#  When number is divisible by 2 so we reduce number and
#  Finding its power
while (num % 2 == 0) :
num = int(num / 2)
power += 1

if (power == 1) :
#  When In case calculated numbers are only one power (2^1)
#  So that is not powerful number
return 0

# Executing the loop under square root of number
factor = 3
while (factor <= math.sqrt(num)) :
# reset power
power = 0
# Calculate factor power
while (num % factor == 0) :
num = int(num / factor)
power += 1

if (power == 1) :
# When factor power is one
return 0

factor += 2

# If calculated resulting number is 1 , so we get powerful number
return num

# Display powerful numbers from 1 to given size
def print_poweful_no(self, size) :
if (size <= 0) :
return

counter = 0
print("\n\tPowerful Number from (1 to ", size ,")\n", end = "")
# Display powerful number form 1 to given size
i = 1
while (i <= size) :
if (self.is_poweful(i) == 1) :
counter += 1
# Display poweful number
print("\t{0}".format(i), end = "")
if (counter % 6 == 0) :
print(end = "\n")

i += 1

print("\n\t---------------------")
print("\t Total : ", counter )

def main() :
obj = PowefulNo()
size = 1000
obj.print_poweful_no(size)

if __name__ == "__main__": main()``````

#### Output

``````	Powerful Number from (1 to  1000 )
1	4	8	9	16	25
27	32	36	49	64	72
81	100	108	121	125	128
144	169	196	200	216	225
243	256	288	289	324	343
361	392	400	432	441	484
500	512	529	576	625	648
675	676	729	784	800	841
864	900	961	968	972	1000

---------------------
Total :  54``````
``````#  Ruby program
#  Powerful Number
class PowefulNo
# Check whether given number is powerful number or not
def is_poweful(num)
#  Define loop control variables
power = 0
factor = 0
if (num % 2 == 0)
#  When number is divisible by 2 so we reduce number and
#  Finding its power
while (num % 2 == 0)
num = num / 2
power += 1
end

if (power == 1)
#  When In case calculated numbers are only one power (2^1)
#  So that is not powerful number
return 0
end

end

# Executing the loop under square root of number
factor = 3
while (factor <= Math.sqrt(num))
# reset power
power = 0
# Calculate factor power
while (num % factor == 0)
num = num / factor
power += 1
end

if (power == 1)
# When factor power is one
return 0
end

factor += 2
end

# If calculated resulting number is 1 , so we get powerful number
return num
end

# Display powerful numbers from 1 to given size
def print_poweful_no(size)
if (size <= 0)
return
end

counter = 0
print("\n\tPowerful Number from (1 to ", size ,")\n")
# Display powerful number form 1 to given size
i = 1
while (i <= size)
if (self.is_poweful(i) == 1)
counter += 1
# Display poweful number
print("\t", i)
if (counter % 6 == 0)
print("\n")
end

end

i += 1
end

print("\n\t---------------------\n")
print("\t Total : ", counter ,"\n")
end

end

def main()
obj = PowefulNo.new()
size = 1000
obj.print_poweful_no(size)
end

main()``````

#### Output

``````	Powerful Number from (1 to 1000)
1	4	8	9	16	25
27	32	36	49	64	72
81	100	108	121	125	128
144	169	196	200	216	225
243	256	288	289	324	343
361	392	400	432	441	484
500	512	529	576	625	648
675	676	729	784	800	841
864	900	961	968	972	1000

---------------------
Total : 54
``````
``````// Scala program
// Powerful Number
class PowefulNo
{
//Check whether given number is powerful number or not
def is_poweful(n: Int): Int = {
var num: Int = n;
// Define loop control variables
var power: Int = 0;
var factor: Int = 0;
if (num % 2 == 0)
{
// When number is divisible by 2 so we reduce number and
// Finding its power
while (num % 2 == 0)
{
num = (num / 2).toInt;
power += 1;
}
if (power == 1)
{
// When In case calculated numbers are only one power (2^1)
// So that is not powerful number
return 0;
}
}
//Executing the loop under square root of number
factor = 3;
while (factor <= Math.sqrt(num))
{
//reset power
power = 0;
//Calculate factor power
while (num % factor == 0)
{
num = (num / factor).toInt;
power += 1;
}
if (power == 1)
{
//When factor power is one
return 0;
}
factor += 2;
}
//If calculated resulting number is 1 , so we get powerful number
return num;
}
//Display powerful numbers from 1 to given size
def print_poweful_no(size: Int): Unit = {
if (size <= 0)
{
return;
}
var counter: Int = 0;
print("\n\tPowerful Number from (1 to " + size + ")\n");
//Display powerful number form 1 to given size
var i: Int = 1;
while (i <= size)
{
if (is_poweful(i) == 1)
{
counter += 1;
//Display poweful number
print("\t" + i);
if (counter % 6 == 0)
{
print("\n");
}
}
i += 1;
}
print("\n\t---------------------\n");
print("\t Total : " + counter + "\n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: PowefulNo = new PowefulNo();
var size: Int = 1000;
obj.print_poweful_no(size);
}
}``````

#### Output

``````	Powerful Number from (1 to 1000)
1	4	8	9	16	25
27	32	36	49	64	72
81	100	108	121	125	128
144	169	196	200	216	225
243	256	288	289	324	343
361	392	400	432	441	484
500	512	529	576	625	648
675	676	729	784	800	841
864	900	961	968	972	1000

---------------------
Total : 54``````
``````import Foundation
// Swift 4 program
// Powerful Number
class PowefulNo
{
//Check whether given number is powerful number or not
func is_poweful(_ n: Int) -> Int
{
var num: Int = n;
// Define loop control variables
var power: Int = 0;
var factor: Int = 0;
if (num % 2 == 0)
{
// When number is divisible by 2 so we reduce number and
// Finding its power
while (num % 2 == 0)
{
num = num / 2;
power += 1;
}
if (power == 1)
{
// When In case calculated numbers are only one power (2^1)
// So that is not powerful number
return 0;
}
}
//Executing the loop under square root of number
factor = 3;
while (factor <= Int(Double(num).squareRoot()))
{
//reset power
power = 0;
//Calculate factor power
while (num % factor == 0)
{
num = num / factor;
power += 1;
}
if (power == 1)
{
//When factor power is one
return 0;
}
factor += 2;
}
//If calculated resulting number is 1 , so we get powerful number
return num;
}
//Display powerful numbers from 1 to given size
func print_poweful_no(_ size: Int)
{
if (size <= 0)
{
return;
}
var counter: Int = 0;
print("\n\tPowerful Number from (1 to ", size ,")\n", terminator: "");
//Display powerful number form 1 to given size
var i: Int = 1;
while (i <= size)
{
if (self.is_poweful(i) == 1)
{
counter += 1;
//Display poweful number
print("\t\(i)", terminator: "");
if (counter % 6 == 0)
{
print("\n", terminator: "");
}
}
i += 1;
}
print("\n\t---------------------\n", terminator: "");
print("\t Total : ", counter ,"\n", terminator: "");
}
}
func main()
{
let obj: PowefulNo = PowefulNo();
let size: Int = 1000;
obj.print_poweful_no(size);
}
main();``````

#### Output

``````	Powerful Number from (1 to  1000 )
1	4	8	9	16	25
27	32	36	49	64	72
81	100	108	121	125	128
144	169	196	200	216	225
243	256	288	289	324	343
361	392	400	432	441	484
500	512	529	576	625	648
675	676	729	784	800	841
864	900	961	968	972	1000

---------------------
Total :  54``````

## Time Complexity

The time complexity of this code is mainly determined by the `print_poweful_no()` function, which iterates through the numbers from 1 to `size` and calls the `is_poweful()` function for each number. The `is_poweful()` function performs factorization up to the square root of the number. Therefore, the time complexity can be approximated as O(n * sqrt(m)), where "n" is the given range (`size`) and "m" is the maximum number in that range (1000 in this case). Since the number of powerful numbers within a range is relatively small, we can consider it to be a sublinear component of the time complexity. Hence, the overall time complexity can be considered close to O(n * sqrt(m)).

## Output Explanation

The code is tested with the range from 1 to 1000. The output shows the powerful numbers found within this range. The numbers are printed in rows of 6 elements each for better readability.

The output displays the powerful numbers from 1 to 1000, and the total count of powerful numbers found in this range is 54.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.