Given a number N, the task is to check whether N has 7 divisors or not.
Examples:
Input: 64
Output: 1
Explanation: 1, 2, 4, 8, 16, 32, 64 -> 7 divisors so output is 1Input: 100
Output: 0
Explanation: 1, 2, 4, 5, 10, 20, 25, 50, 100 -> 8 divisors so output is 0Input: 729
Output: 1
Explanation: 1, 2, 4, 8, 16, 32, 64 -> 7 divisors so output is 1
Approach: The problem can be solved based on the following mathematical observation:
The prime factorization of a number is:
N = p1e1 * p2e2 * . . . * pnen
So number of divisors = ( e1 + 1 ) * (e2 + 1) *. . . * (en + 1).In this case, number of divisors = 7 .
So, ( e1 + 1 ) * (e2 + 1) *. . . * (en + 1) = 77 is multiplication of at most 2 natural numbers.
So, it can be only written as ( e1 + 1 ) * (e2 + 1) = 1 * 7
So, e1 = 0 & e2 = 6 from above equation.
So, it is clear that for 7 divisors only one case is possible and that is (prime number)6. Follow the steps to solve the problem:
- Check if N(1/6) is a prime number or not.
- If it is prime number then output “Yes”.
- Otherwise, the output will be “No”.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to check number of// divisors are 7 or notint sevenDivisors(int N){ // Using power function to get 6th Root int k = pow(N, 1 / 6.); // Using power function to get // 6th power of k int res = pow(k, 6); // If res is equal to given number // N then return 1 if (N == res) return 1; return 0;}// Driver codeint main(){ int N = 64; // Function call bool ans = sevenDivisors(N); if (ans) cout << "Yes"; else cout << "No"; return 0;} |
Java
// Java code to implement the approachimport java.io.*;class GFG { public boolean sevenDivisors(int N) { // Using power function to get 6th Root int k = (int)Math.pow(N, 1 / 6.); // Using power function to get // 6th power of k int res = (int)Math.pow(k, 6); // If res is equal to given number // N then return 1 if (N == res) return true; return false; } public static void main(String[] args) { int N = 64; // Function call GFG g1 = new GFG(); boolean ans = g1.sevenDivisors(N); if (ans) System.out.println("Yes"); else System.out.println("No"); }}// This code is contributed by patildhanu4111999. |
Python3
# Python3 code to implement the approach# Function to check number of# divisors are 7 or notdef sevenDivisors(N) : # Using power function to get 6th Root k = pow(N, 1 / 6); # Using power function to get # 6th power of k res = pow(k, 6); # If res is equal to given number # N then return 1 if (N == res) : return 1; return 0;# Driver codeif __name__ == "__main__" : N = 64; # Function call ans = sevenDivisors(N); if (ans) : print("Yes"); else : print("No"); # This code is contributed by AnkThon |
C#
// C# code to implement the approachusing System;public class GFG { public bool sevenDivisors(int N) { // Using power function to get 6th Root int k = (int)Math.Pow(N, 1 / 6.0); // Using power function to get // 6th power of k int res = (int)Math.Pow(k, 6); // If res is equal to given number // N then return 1 if (N == res) return true; return false; } public static void Main(String[] args) { int N = 64; // Function call GFG g1 = new GFG(); bool ans = g1.sevenDivisors(N); if (ans) Console.WriteLine("Yes"); else Console.WriteLine("No"); }}// This code contributed by shikhasingrajput |
Javascript
<script>// Javascript code to implement the approach// Function to check number of// divisors are 7 or notfunction sevenDivisors(N){ // Using power function to get 6th Root let k = Math.pow(N, 1 / 6.); // Using power function to get // 6th power of k let res = Math.pow(k, 6); // If res is equal to given number // N then return 1 if (N == res) return 1; return 0;}// Driver code let N = 64; // Function call let ans = sevenDivisors(N); if (ans) document.write('YES',"</br>"); else document.write('No',"</br>"); </script> |
Yes
Time Complexity: O(logN)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
