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:
-
The function
is_poweful(int num)
checks whether a given numbernum
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 thepower
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. -
The function
print_poweful_no(int size)
takes a parametersize
, which represents the upper limit of the range. It iterates through the numbers from 1 tosize
and uses theis_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. -
In the
main()
function, a test case is performed where the functionprint_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.
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.
New Comment