Skip to main content

Check if number is a prime power number

The given problem is to check if a given number is a prime power number. A prime power number is a number that can be expressed as the power of a prime number, where the exponent is greater than or equal to 2. For example, 4 (2^2), 27 (3^3), and 125 (5^3) are prime power numbers, but 6, 30, and 100 are not.

Example Explanation

Let's take an example to illustrate the concept. Consider the number 27.

Step 1: We find all prime numbers up to a certain limit (in this code, the limit is 1000001) using the Sieve of Eratosthenes algorithm. In this case, we would find the primes as 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, and so on.

Step 2: We check each prime number if it divides 27. In this case, 3 is a prime number, and it divides 27. So, we store 3 as the base and initialize the power as 0.

Step 3: We keep dividing 27 by 3 until it is no longer divisible by 3. The number of times we successfully divide is the power. In this case, 27 can be divided by 3 three times (27 / 3 = 9, 9 / 3 = 3, 3 / 3 = 1), so the power is 3.

Step 4: Finally, we check if the number has been reduced to 1. If it is 1, then the original number is a prime power number, and we print the base and power. Otherwise, it is not a prime power number.

Standard Pseudocode

function sieve_of_eratosthenes(collection)
    Initialize an array of size collection with 1's representing potential prime numbers
    Set the first two elements to 0 (0 and 1 are not prime)

    for i from 2 to sqrt(collection)
        if collection[i] is prime
            Mark all multiples of i as non-prime in the collection

function is_prime_power(collection, num)
    Initialize variables: status = 0, num_base = 0, num_power = 0, temp = 0
    Calculate sqrt_value as the square root of num

    for i from 2 to sqrt_value and num_base is 0
        if collection[i] is prime and num is divisible by i
            Set num_base to i
            Set temp to num

            while temp is divisible by i
                Increment num_power
                Update temp by dividing it by i

            if temp is 1
                Set status to 1

    if status is 1
        Print "Number [num] is a prime power number of (num_base^num_power)"
    else
        Print "Number [num] is not a prime power number"

Algorithm Explanation

  1. The sieve_of_eratosthenes function initializes an array of potential prime numbers and then marks all non-prime numbers using the Sieve of Eratosthenes algorithm.

  2. The is_prime_power function takes the array of prime numbers and a number num as input. It initializes variables to store the base and power of the prime power number and calculates the square root of num for optimization.

  3. It then iterates through each prime number up to the square root of num and checks if num is divisible by that prime. If it is, it sets the base to that prime and calculates the power by dividing num repeatedly by the base until it is no longer divisible.

  4. If the final value of temp (after dividing by the base) is 1, it means num is a prime power number. In that case, it sets the status variable to 1.

  5. Finally, it checks the value of status and prints the appropriate message indicating whether num is a prime power number or not.

Code Solution

Here given code implementation process.

// C program
// Check if number is a prime power number
#include <stdio.h>
#include <math.h>
#define SIZE 1000001

//Find all prime numbers under 1000001 
void sieve_of_eratosthenes(int collection[])
{
	// Loop controlling variables
	int i = 0;
	int j = 1;
	// Initial two numbers are not prime (0 and 1)
	collection[i] = 0;
	collection[j] = 0;
	// Set the initial (2 to n element is prime)
	for (i = 2; i < SIZE; ++i)
	{
		collection[i] = 1;
	}
	// Initial 0 and 1 are not prime
	// We start to 2
	for (i = 2; i * i < SIZE; ++i)
	{
		if (collection[i] == 1)
		{
			//When i is prime number
			//Modify the prime status of all next multiplier of location i
			for (j = i * i; j < SIZE; j += i)
			{
				collection[j] = 0;
			}
		}
	}
}
void is_prime_power(int collection[], int num)
{
	int status = 0;
	int num_base = 0;
	int num_power = 0;
	int temp = 0;
	int sqrt_value = sqrt(num);
	for (int i = 2; i <= sqrt_value && num_base == 0; ++i)
	{
		if (collection[i] == 1 && num % i == 0)
		{
			// When [i] is prime number and number is divisible of i
			// We get base
			num_base = i;
			temp = num;
			// Find power
			while (temp % i == 0)
			{
				num_power++;
				temp = temp / i;
			}
			if (temp == 1)
			{
				status = 1;
			}
		}
	}
	if (status == 1)
	{
		printf("\n Number [%d] is prime power number of (%d^%d)", num, num_base, num_power);
	}
	else
	{
		printf("\n Number [%d] is not prime power number", num);
	}
}
int main()
{
	//This is used to store prime number status
	int collection[SIZE];
	//Find find prime number
	sieve_of_eratosthenes(collection);
	//Test case
	is_prime_power(collection, 9);
	is_prime_power(collection, 1331);
	is_prime_power(collection, 2187);
	is_prime_power(collection, 81);
	is_prime_power(collection, 452);
	is_prime_power(collection, 361);
	is_prime_power(collection, 512);
	return 0;
}

Output

 Number [9] is prime power number of (3^2)
 Number [1331] is prime power number of (11^3)
 Number [2187] is prime power number of (3^7)
 Number [81] is prime power number of (3^4)
 Number [452] is not prime power number
 Number [361] is prime power number of (19^2)
 Number [512] is prime power number of (2^9)
// Java program 
// Check if number is a prime power number
class PrimePower
{
	//Determine if the given number is the prime base power or not
	public void is_prime_power(boolean[] collection, int num)
	{
		boolean status = false;
		//Define useful resultant variable
		int num_base = 0;
		int num_power = 0;
		int temp = 0;
		int sqrt_value = (int) Math.sqrt(num);
		for (int i = 2; i <= sqrt_value && num_base == 0; ++i)
		{
			if (collection[i] == true && num % i == 0)
			{
				// When [i] is prime number and number is divisible of i
				// We get base
				num_base = i;
				temp = num;
				// Find power
				while (temp % i == 0)
				{
					num_power++;
					temp = temp / i;
				}
				if (temp == 1)
				{
					status = true;
				}
			}
		}
		if (status == true)
		{
			System.out.print("\n Number [" + num + "] is prime power number of (" + num_base + "^" + num_power + ")");
		}
		else
		{
			System.out.print("\n Number [" + num + "] is not prime power number");
		}
	}
	//Find all prime numbers under 1000001 
	public void sieve_of_eratosthenes(boolean[] collection, int size)
	{
		// Loop controlling variables
		int i = 0;
		int j = 1;
		// Initial two numbers are not prime (0 and 1)
		collection[i] = false;
		collection[j] = false;
		// Set the initial (2 to n element is prime)
		for (i = 2; i < size; ++i)
		{
			collection[i] = true;
		}
		// Initial 0 and 1 are not prime
		// We start to 2
		for (i = 2; i * i < size; ++i)
		{
			if (collection[i] == true)
			{
				//When i is prime number
				//Modify the prime status of all next multiplier of location i
				for (j = i * i; j < size; j += i)
				{
					collection[j] = false;
				}
			}
		}
	}
	public static void main(String[] args)
	{
		PrimePower obj = new PrimePower();
		int size = 1000001;
		//This is used to store prime number status
		boolean[] collection = new boolean[size];
		//Find find prime number
		obj.sieve_of_eratosthenes(collection, size);
		//Test case
		obj.is_prime_power(collection, 9);
		obj.is_prime_power(collection, 1331);
		obj.is_prime_power(collection, 2187);
		obj.is_prime_power(collection, 81);
		obj.is_prime_power(collection, 452);
		obj.is_prime_power(collection, 361);
		obj.is_prime_power(collection, 512);
	}
}

Output

 Number [9] is prime power number of (3^2)
 Number [1331] is prime power number of (11^3)
 Number [2187] is prime power number of (3^7)
 Number [81] is prime power number of (3^4)
 Number [452] is not prime power number
 Number [361] is prime power number of (19^2)
 Number [512] is prime power number of (2^9)
//Include header file
#include <iostream>

#include<math.h>

using namespace std;
// C++ program 
// Check if number is a prime power number
class PrimePower
{
	public:
		//Determine if the given number is the prime base power or not
		void is_prime_power(bool collection[], int num)
		{
			bool status = false;
			//Define useful resultant variable
			int num_base = 0;
			int num_power = 0;
			int temp = 0;
			int sqrt_value = (int) sqrt(num);
			for (int i = 2; i <= sqrt_value && num_base == 0; ++i)
			{
				if (collection[i] == true && num % i == 0)
				{
					// When [i] is prime number and number is divisible of i
					// We get base
					num_base = i;
					temp = num;
					// Find power
					while (temp % i == 0)
					{
						num_power++;
						temp = temp / i;
					}
					if (temp == 1)
					{
						status = true;
					}
				}
			}
			if (status == true)
			{
				cout << "\n Number [" << num << "] is prime power number of (" << num_base << "^" << num_power << ")";
			}
			else
			{
				cout << "\n Number [" << num << "] is not prime power number";
			}
		}
	//Find all prime numbers under 1000001 
	void sieve_of_eratosthenes(bool collection[], int size)
	{
		// Loop controlling variables
		int i = 0;
		int j = 1;
		// Initial two numbers are not prime (0 and 1)
		collection[i] = false;
		collection[j] = false;
		// Set the initial (2 to n element is prime)
		for (i = 2; i < size; ++i)
		{
			collection[i] = true;
		}
		// Initial 0 and 1 are not prime
		// We start to 2
		for (i = 2; i *i < size; ++i)
		{
			if (collection[i] == true)
			{
				//When i is prime number
				//Modify the prime status of all next multiplier of location i
				for (j = i *i; j < size; j += i)
				{
					collection[j] = false;
				}
			}
		}
	}
};
int main()
{
	PrimePower obj = PrimePower();
	int size = 1000001;
	//This is used to store prime number status
	bool collection[size];
	//Find find prime number
	obj.sieve_of_eratosthenes(collection, size);
	//Test case
	obj.is_prime_power(collection, 9);
	obj.is_prime_power(collection, 1331);
	obj.is_prime_power(collection, 2187);
	obj.is_prime_power(collection, 81);
	obj.is_prime_power(collection, 452);
	obj.is_prime_power(collection, 361);
	obj.is_prime_power(collection, 512);
	return 0;
}

Output

 Number [9] is prime power number of (3^2)
 Number [1331] is prime power number of (11^3)
 Number [2187] is prime power number of (3^7)
 Number [81] is prime power number of (3^4)
 Number [452] is not prime power number
 Number [361] is prime power number of (19^2)
 Number [512] is prime power number of (2^9)
//Include namespace system
using System;
// C# program 
// Check if number is a prime power number
class PrimePower
{
	//Determine if the given number is the prime base power or not
	public void is_prime_power(Boolean[] collection, int num)
	{
		Boolean status = false;
		//Define useful resultant variable
		int num_base = 0;
		int num_power = 0;
		int temp = 0;
		int sqrt_value = (int) Math.Sqrt(num);
		for (int i = 2; i <= sqrt_value && num_base == 0; ++i)
		{
			if (collection[i] == true && num % i == 0)
			{
				// When [i] is prime number and number is divisible of i
				// We get base
				num_base = i;
				temp = num;
				// Find power
				while (temp % i == 0)
				{
					num_power++;
					temp = temp / i;
				}
				if (temp == 1)
				{
					status = true;
				}
			}
		}
		if (status == true)
		{
			Console.Write("\n Number [" + num + "] is prime power number of (" + num_base + "^" + num_power + ")");
		}
		else
		{
			Console.Write("\n Number [" + num + "] is not prime power number");
		}
	}
	//Find all prime numbers under 1000001 
	public void sieve_of_eratosthenes(Boolean[] collection, int size)
	{
		// Loop controlling variables
		int i = 0;
		int j = 1;
		// Initial two numbers are not prime (0 and 1)
		collection[i] = false;
		collection[j] = false;
		// Set the initial (2 to n element is prime)
		for (i = 2; i < size; ++i)
		{
			collection[i] = true;
		}
		// Initial 0 and 1 are not prime
		// We start to 2
		for (i = 2; i * i < size; ++i)
		{
			if (collection[i] == true)
			{
				//When i is prime number
				//Modify the prime status of all next multiplier of location i
				for (j = i * i; j < size; j += i)
				{
					collection[j] = false;
				}
			}
		}
	}
	public static void Main(String[] args)
	{
		PrimePower obj = new PrimePower();
		int size = 1000001;
		//This is used to store prime number status
		Boolean[] collection = new Boolean[size];
		//Find find prime number
		obj.sieve_of_eratosthenes(collection, size);
		//Test case
		obj.is_prime_power(collection, 9);
		obj.is_prime_power(collection, 1331);
		obj.is_prime_power(collection, 2187);
		obj.is_prime_power(collection, 81);
		obj.is_prime_power(collection, 452);
		obj.is_prime_power(collection, 361);
		obj.is_prime_power(collection, 512);
	}
}

Output

 Number [9] is prime power number of (3^2)
 Number [1331] is prime power number of (11^3)
 Number [2187] is prime power number of (3^7)
 Number [81] is prime power number of (3^4)
 Number [452] is not prime power number
 Number [361] is prime power number of (19^2)
 Number [512] is prime power number of (2^9)
<?php
// Php program 
// Check if number is a prime power number
class PrimePower
{
    //Determine if the given number is the prime base power or not
    public  function is_prime_power( & $collection, $num)
    {
        $status = false;
        //Define useful resultant variable
        $num_base = 0;
        $num_power = 0;
        $temp = 0;
        $sqrt_value = (sqrt($num));
        for ($i = 2; $i <= $sqrt_value && $num_base == 0; ++$i)
        {
            if ($collection[$i] == true && $num % $i == 0)
            {
                // When [i] is prime number and number is divisible of i
                // We get base
                $num_base = $i;
                $temp = $num;
                // Find power
                while ($temp % $i == 0)
                {
                    $num_power++;
                    $temp = intval($temp / $i);
                }
                if ($temp == 1)
                {
                    $status = true;
                }
            }
        }
        if ($status == true)
        {
            echo "\n Number [". $num ."] is prime power number of (". $num_base ."^". $num_power .")";
        }
        else
        {
            echo "\n Number [". $num ."] is not prime power number";
        }
    }
    //Find all prime numbers under 1000001 
    public  function sieve_of_eratosthenes( & $collection, $size)
    {
        // Loop controlling variables
        $i = 0;
        $j = 1;
        // Initial two numbers are not prime (0 and 1)
        $collection[$i] = false;
        $collection[$j] = false;
        // Initial 0 and 1 are not prime
        // We start to 2
        for ($i = 2; $i * $i < $size; ++$i)
        {
            if ($collection[$i] == true)
            {
                //When i is prime number
                //Modify the prime status of all next multiplier of location i
                for ($j = $i * $i; $j < $size; $j += $i)
                {
                    $collection[$j] = false;
                }
            }
        }
    }
}

function main()
{
    $obj = new PrimePower();
    $size = 1000001;
    //This is used to store prime number status
    $collection = array_fill(0, $size, true);
    //Find find prime number
    $obj->sieve_of_eratosthenes($collection, $size);
    //Test case
    $obj->is_prime_power($collection, 9);
    $obj->is_prime_power($collection, 1331);
    $obj->is_prime_power($collection, 2187);
    $obj->is_prime_power($collection, 81);
    $obj->is_prime_power($collection, 452);
    $obj->is_prime_power($collection, 361);
    $obj->is_prime_power($collection, 512);
}
main();

Output

 Number [9] is prime power number of (3^2)
 Number [1331] is prime power number of (11^3)
 Number [2187] is prime power number of (3^7)
 Number [81] is prime power number of (3^4)
 Number [452] is not prime power number
 Number [361] is prime power number of (19^2)
 Number [512] is prime power number of (2^9)
// Node Js program 
// Check if number is a prime power number

class PrimePower
{
	//Determine if the given number is the prime base power or not
	is_prime_power(collection, num)
	{
		var status = false;
		//Define useful resultant variable
		var num_base = 0;
		var num_power = 0;
		var temp = 0;
		var sqrt_value = (Math.sqrt(num));
		for (var i = 2; i <= sqrt_value && num_base == 0; ++i)
		{
			if (collection[i] == true && num % i == 0)
			{
				// When [i] is prime number and number is divisible of i
				// We get base
				num_base = i;
				temp = num;
				// Find power
				while (temp % i == 0)
				{
					num_power++;
					temp = parseInt(temp / i);
				}
				if (temp == 1)
				{
					status = true;
				}
			}
		}
		if (status == true)
		{
			process.stdout.write("\n Number [" + num + "] is prime power number of (" + num_base + "^" + num_power + ")");
		}
		else
		{
			process.stdout.write("\n Number [" + num + "] is not prime power number");
		}
	}
	//Find all prime numbers under 1000001 
	sieve_of_eratosthenes(collection, size)
	{
		// Loop controlling variables
		var i = 0;
		var j = 1;
		// Initial two numbers are not prime (0 and 1)
		collection[i] = false;
		collection[j] = false;
		// Initial 0 and 1 are not prime
		// We start to 2
		for (i = 2; i * i < size; ++i)
		{
			if (collection[i] == true)
			{
				//When i is prime number
				//Modify the prime status of all next multiplier of location i
				for (j = i * i; j < size; j += i)
				{
					collection[j] = false;
				}
			}
		}
	}
}

function main()
{
	var obj = new PrimePower();
	var size = 1000001;
	//This is used to store prime number status
	var collection = Array(size).fill(true);
	//Find find prime number
	obj.sieve_of_eratosthenes(collection, size);
	//Test case
	obj.is_prime_power(collection, 9);
	obj.is_prime_power(collection, 1331);
	obj.is_prime_power(collection, 2187);
	obj.is_prime_power(collection, 81);
	obj.is_prime_power(collection, 452);
	obj.is_prime_power(collection, 361);
	obj.is_prime_power(collection, 512);
}
main();

Output

 Number [9] is prime power number of (3^2)
 Number [1331] is prime power number of (11^3)
 Number [2187] is prime power number of (3^7)
 Number [81] is prime power number of (3^4)
 Number [452] is not prime power number
 Number [361] is prime power number of (19^2)
 Number [512] is prime power number of (2^9)
import math

#  Python 3 program 
#  Check if number is a prime power number

class PrimePower :
	# Determine if the given number is the prime base power or not
	def is_prime_power(self, collection, num) :
		status = False
		# Define useful resultant variable
		num_base = 0
		num_power = 0
		temp = 0
		sqrt_value = (math.sqrt(num))
		i = 2
		while (i <= sqrt_value and num_base == 0) :
			if (collection[i] == True and num % i == 0) :
				#  When [i] is prime number and number is divisible of i
				#  We get base
				num_base = i
				temp = num
				#  Find power
				while (temp % i == 0) :
					num_power += 1
					temp = int(temp / i)
				
				if (temp == 1) :
					status = True
				
			
			i += 1
		
		if (status == True) :
			print("\n Number [{0}] is prime power number of ({1}^{2})".format(num,num_base,num_power), end = "")
		else :
			print("\n Number [{0}] is not prime power number".format(num), end = "")
		
	
	# Find all prime numbers under 1000001 
	def sieve_of_eratosthenes(self, collection, size) :
		#  Loop controlling variables
		i = 0
		j = 1
		#  Initial two numbers are not prime (0 and 1)
		collection[i] = False
		collection[j] = False
		#  Initial 0 and 1 are not prime
		#  We start to 2
		i = 2
		while (i * i < size) :
			if (collection[i] == True) :
				# When i is prime number
				# Modify the prime status of all next multiplier of location i
				j = i * i
				while (j < size) :
					collection[j] = False
					j += i
				
			
			i += 1
		
	

def main() :
	obj = PrimePower()
	size = 1000001
	# This is used to store prime number status
	collection = [True] * (size)
	# Find find prime number
	obj.sieve_of_eratosthenes(collection, size)
	# Test case
	obj.is_prime_power(collection, 9)
	obj.is_prime_power(collection, 1331)
	obj.is_prime_power(collection, 2187)
	obj.is_prime_power(collection, 81)
	obj.is_prime_power(collection, 452)
	obj.is_prime_power(collection, 361)
	obj.is_prime_power(collection, 512)

if __name__ == "__main__": main()

Output

 Number [9] is prime power number of (3^2)
 Number [1331] is prime power number of (11^3)
 Number [2187] is prime power number of (3^7)
 Number [81] is prime power number of (3^4)
 Number [452] is not prime power number
 Number [361] is prime power number of (19^2)
 Number [512] is prime power number of (2^9)
#  Ruby program 
#  Check if number is a prime power number
class PrimePower 
	# Determine if the given number is the prime base power or not
	def is_prime_power(collection, num) 
		status = false
		# Define useful resultant variable
		num_base = 0
		num_power = 0
		temp = 0
		sqrt_value = (Math.sqrt(num)).to_i
		i = 2
		while (i <= sqrt_value && num_base == 0) 
			if (collection[i] == true && num % i == 0) 
				#  When [i] is prime number and number is divisible of i
				#  We get base
				num_base = i
				temp = num
				#  Find power
				while (temp % i == 0) 
					num_power += 1
					temp = temp / i
				end

				if (temp == 1) 
					status = true
				end

			end

			i += 1
		end

		if (status == true) 
			print("\n Number [", num ,"] is prime power number of (", num_base ,"^", num_power ,")")
		else 
			print("\n Number [", num ,"] is not prime power number")
		end

	end

	# Find all prime numbers under 1000001 
	def sieve_of_eratosthenes(collection, size) 
		#  Loop controlling variables
		i = 0
		j = 1
		#  Initial two numbers are not prime (0 and 1)
		collection[i] = false
		collection[j] = false
		#  Initial 0 and 1 are not prime
		#  We start to 2
		i = 2
		while (i * i < size) 
			if (collection[i] == true) 
				# When i is prime number
				# Modify the prime status of all next multiplier of location i
				j = i * i
				while (j < size) 
					collection[j] = false
					j += i
				end

			end

			i += 1
		end

	end

end

def main() 
	obj = PrimePower.new()
	size = 1000001
	# This is used to store prime number status
	collection = Array.new(size) {true}
	# Find find prime number
	obj.sieve_of_eratosthenes(collection, size)
	# Test case
	obj.is_prime_power(collection, 9)
	obj.is_prime_power(collection, 1331)
	obj.is_prime_power(collection, 2187)
	obj.is_prime_power(collection, 81)
	obj.is_prime_power(collection, 452)
	obj.is_prime_power(collection, 361)
	obj.is_prime_power(collection, 512)
end

main()

Output

 Number [9] is prime power number of (3^2)
 Number [1331] is prime power number of (11^3)
 Number [2187] is prime power number of (3^7)
 Number [81] is prime power number of (3^4)
 Number [452] is not prime power number
 Number [361] is prime power number of (19^2)
 Number [512] is prime power number of (2^9)
// Scala program 
// Check if number is a prime power number
class PrimePower
{
	//Determine if the given number is the prime base power or not
	def is_prime_power(collection: Array[Boolean], num: Int): Unit = {
		var status: Boolean = false;
		//Define useful resultant variable
		var num_base: Int = 0;
		var num_power: Int = 0;
		var temp: Int = 0;
		var sqrt_value: Int = (Math.sqrt(num)).toInt;
		var i: Int = 2;
		while (i <= sqrt_value && num_base == 0)
		{
			if (collection(i) == true && num % i == 0)
			{
				// When [i] is prime number and number is divisible of i
				// We get base
				num_base = i;
				temp = num;
				// Find power
				while (temp % i == 0)
				{
					num_power += 1;
					temp = (temp / i).toInt;
				}
				if (temp == 1)
				{
					status = true;
				}
			}
			i += 1;
		}
		if (status == true)
		{
			print("\n Number [" + num + "] is prime power number of (" + num_base + "^" + num_power + ")");
		}
		else
		{
			print("\n Number [" + num + "] is not prime power number");
		}
	}
	//Find all prime numbers under 1000001 
	def sieve_of_eratosthenes(collection: Array[Boolean], size: Int): Unit = {
		// Loop controlling variables
		var i: Int = 0;
		var j: Int = 1;
		// Initial two numbers are not prime (0 and 1)
		collection(i) = false;
		collection(j) = false;
		// Initial 0 and 1 are not prime
		// We start to 2
		i = 2;
		while (i * i < size)
		{
			if (collection(i) == true)
			{
				//When i is prime number
				//Modify the prime status of all next multiplier of location i
				j = i * i;
				while (j < size)
				{
					collection(j) = false;
					j += i;
				}
			}
			i += 1;
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var obj: PrimePower = new PrimePower();
		var size: Int = 1000001;
		//This is used to store prime number status
		var collection: Array[Boolean] = Array.fill[Boolean](size)(true);
		//Find find prime number
		obj.sieve_of_eratosthenes(collection, size);
		//Test case
		obj.is_prime_power(collection, 9);
		obj.is_prime_power(collection, 1331);
		obj.is_prime_power(collection, 2187);
		obj.is_prime_power(collection, 81);
		obj.is_prime_power(collection, 452);
		obj.is_prime_power(collection, 361);
		obj.is_prime_power(collection, 512);
	}
}

Output

 Number [9] is prime power number of (3^2)
 Number [1331] is prime power number of (11^3)
 Number [2187] is prime power number of (3^7)
 Number [81] is prime power number of (3^4)
 Number [452] is not prime power number
 Number [361] is prime power number of (19^2)
 Number [512] is prime power number of (2^9)
import Foundation
// Swift 4 program 
// Check if number is a prime power number
class PrimePower
{
	//Determine if the given number is the prime base power or not
	func is_prime_power(_ collection: [Bool], _ num: Int)
	{
		var status: Bool = false;
		//Define useful resultant variable
		var num_base: Int = 0;
		var num_power: Int = 0;
		var temp: Int = 0;
		let sqrt_value: Int = Int(sqrt(Double(num)));
		var i: Int = 2;
		while (i <= sqrt_value && num_base == 0)
		{
			if (collection[i] == true && num % i == 0)
			{
				// When [i]is prime number and number is divisible of i
				// We get base
				num_base = i;
				temp = num;
				// Find power
				while (temp % i == 0)
				{
					num_power += 1;
					temp = temp / i;
				}
				if (temp == 1)
				{
					status = true;
				}
			}
			i += 1;
		}
		if (status == true)
		{
			print("\n Number [", num, "] is prime power number of (", num_base, "^", num_power, ")", terminator: "");
		}
		else
		{
			print("\n Number [", num, "] is not prime power number", terminator: "");
		}
	}
	//Find all prime numbers under 1000001 
	func sieve_of_eratosthenes(_ collection: inout[Bool], _ size: Int)
	{
		// Loop controlling variables
		var i: Int = 0;
		var j: Int = 1;
		// Initial two numbers are not prime (0 and 1)
		collection[i] = false;
		collection[j] = false;
		// Initial 0 and 1 are not prime
		// We start to 2
		i = 2;
		while (i * i < size)
		{
			if (collection[i] == true)
			{
				//When i is prime number
				//Modify the prime status of all next multiplier of location i
				j = i * i;
				while (j < size)
				{
					collection[j] = false;
					j += i;
				}
			}
			i += 1;
		}
	}
}
func main()
{
	let obj: PrimePower = PrimePower();
	let size: Int = 1000001;
	//This is used to store prime number status
	var collection: [Bool] = Array(repeating: true, count: size);
	//Find find prime number
	obj.sieve_of_eratosthenes( &collection, size);
	//Test case
	obj.is_prime_power(collection, 9);
	obj.is_prime_power(collection, 1331);
	obj.is_prime_power(collection, 2187);
	obj.is_prime_power(collection, 81);
	obj.is_prime_power(collection, 452);
	obj.is_prime_power(collection, 361);
	obj.is_prime_power(collection, 512);
}
main();

Output

 Number [ 9 ] is prime power number of ( 3 ^ 2 )
 Number [ 1331 ] is prime power number of ( 11 ^ 3 )
 Number [ 2187 ] is prime power number of ( 3 ^ 7 )
 Number [ 81 ] is prime power number of ( 3 ^ 4 )
 Number [ 452 ] is not prime power number
 Number [ 361 ] is prime power number of ( 19 ^ 2 )
 Number [ 512 ] is prime power number of ( 2 ^ 9 )

Resultant Output Explanation

The provided code gives the output for several test cases. For example, for the input 9, the code correctly identifies it as a prime power number of 3^2. Similarly, for other inputs like 1331, 2187, and 512, the code identifies the correct base and power.

For non-prime power numbers like 452, the code correctly identifies that they are not prime power numbers.

Time Complexity

  • The sieve_of_eratosthenes function runs in O(n log log n) time complexity, where n is the limit (SIZE in this case).
  • The is_prime_power function iterates up to the square root of num, which takes O(sqrt(num)) operations.
  • Inside the loop, the while loop divides num by a prime number, which can take at most log(num) operations in the worst case (when num is a large prime power number).

Overall, the time complexity of the entire code is approximately O(n log log n + T * sqrt(num) * log(num)), where T is the number of test cases.

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