Given an integer 
. The task is to find the superpower from the factorization of .
The Superpower is the highest power among the power of primes in the factorisation of a number n.
Examples:
Input : n = 32 Output : 5 Input : n = 240 Output : 4
For finding the superpower of any given number , we have to complete the factorisation of n, and find out highest power among all of the prime factors.
Note: Using Sieve for the purpose of storing list of primes is useful in terms of optimization.
Algorithm :
- Iterate over primes and calculate the factorization of n.
- For each prime among the stored list of primes and which is also a factor of n,
find its power and check it for super power.
Below is the implementation of the above approach:
C++
// CPP for finding super power of n#include <bits/stdc++.h>#define MAX 100000using namespace std;// global hash for primebool prime[100002];// sieve method for storing a list of primevoid SieveOfEratosthenes(){ memset(prime, true, sizeof(prime)); for (int p = 2; p * p <= MAX; p++) if (prime[p] == true) for (int i = p * 2; i <= MAX; i += p) prime[i] = false;}// function to return super powerint superpower(int n){ SieveOfEratosthenes(); int superPower = 0, factor = 0; int i = 2; // find the super power while (n > 1 && i <= MAX) { if (prime[i]) { factor = 0; while (n % i == 0 && n > 1) { factor++; n = n / i; } if (superPower < factor) superPower = factor; } i++; } return superPower;}// Driver programint main(){ int n = 256; cout << superpower(n); return 0;} |
Java
// Java for finding super power of n class GFG{ static int MAX=100000; // global hash for prime static boolean[] prime=new boolean[100002]; // sieve method for storing a list of prime static void SieveOfEratosthenes() { for (int p = 2; p * p <= MAX; p++) if (prime[p] == false) for (int i = p * 2; i <= MAX; i += p) prime[i] = true; } // function to return super power static int superpower(int n) { SieveOfEratosthenes(); int superPower = 0, factor = 0; int i = 2; // find the super power while (n > 1 && i <= MAX) { if (!prime[i]) { factor = 0; while (n % i == 0 && n > 1) { factor++; n = n / i; } if (superPower < factor) superPower = factor; } i++; } return superPower; } // Driver program public static void main(String[] args) { int n = 256; System.out.println(superpower(n));} }// This code is contributed by mits |
Python3
# Python3 for finding super# power of nMAX = 100000;# global hash for primeprime = [True] * 100002;# sieve method for storing# a list of primedef SieveOfEratosthenes(): p = 2; while(p * p <= MAX): if (prime[p] == True): i = p * 2; while(i <= MAX): prime[i] = False; i += p; p += 1;# function to return super powerdef superpower(n): SieveOfEratosthenes(); superPower = 0; factor = 0; i = 2; # find the super power while (n > 1 and i <= MAX): if (prime[i]): factor = 0; while (n % i == 0 and n > 1): factor += 1; n = int(n / i); if (superPower < factor): superPower = factor; i += 1; return superPower;# Driver Coden = 256;print(superpower(n));# This code is contributed by mits |
C#
// C# for finding super power of n class GFG{ static int MAX = 100000; // global hash for prime static bool[] prime = new bool[100002]; // sieve method for storing// a list of prime static void SieveOfEratosthenes() { for (int p = 2; p * p <= MAX; p++) if (prime[p] == false) for (int i = p * 2; i <= MAX; i += p) prime[i] = true; } // function to return super power static int superpower(int n) { SieveOfEratosthenes(); int superPower = 0, factor = 0; int i = 2; // find the super power while (n > 1 && i <= MAX) { if (!prime[i]) { factor = 0; while (n % i == 0 && n > 1) { factor++; n = n / i; } if (superPower < factor) superPower = factor; } i++; } return superPower; } // Driver Code static void Main() { int n = 256; System.Console.WriteLine(superpower(n));} }// This code is contributed by mits |
PHP
<?php// PHP for finding super power of n$MAX = 100000;// global hash for prime$prime = array_fill(0, 100002, true);// sieve method for storing// a list of primefunction SieveOfEratosthenes(){ global $MAX, $prime; for ($p = 2; $p * $p <= $MAX; $p++) if ($prime[$p] == true) for ($i = $p * 2; $i <= $MAX; $i += $p) $prime[$i] = false;}// function to return super powerfunction superpower($n){ SieveOfEratosthenes(); global $MAX, $prime; $superPower = 0; $factor = 0; $i = 2; // find the super power while ($n > 1 && $i <= $MAX) { if ($prime[$i]) { $factor = 0; while ($n % $i == 0 && $n > 1) { $factor++; $n = $n / $i; } if ($superPower < $factor) $superPower = $factor; } $i++; } return $superPower;}// Driver Code$n = 256;echo superpower($n);// This code is contributed by mits?> |
Javascript
<script>// Javascript for finding super power of nvar MAX = 100000;// global hash for primevar prime = Array(100002).fill(true);// sieve method for storing a list of primefunction SieveOfEratosthenes(){ for (var p = 2; p * p <= MAX; p++) if (prime[p] == true) for (var i = p * 2; i <= MAX; i += p) prime[i] = false;}// function to return super powerfunction superpower(n){ SieveOfEratosthenes(); var superPower = 0, factor = 0; var i = 2; // find the super power while (n > 1 && i <= MAX) { if (prime[i]) { factor = 0; while (n % i == 0 && n > 1) { factor++; n = n / i; } if (superPower < factor) superPower = factor; } i++; } return superPower;}// Driver programvar n = 256;document.write( superpower(n));</script> |
Output:
8
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
