Skip to main content

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.

Last updated on by Kalkicode




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.

New Comment