Дати број одреди да ли је исправан Хиперсавршен број .
Број н се назива к-хиперперфектним ако: н = 1 + к?иди где су сви дису прави делиоци н.
Узимајући к = 1 добићемо савршени бројеви .
Првих неколико к-хиперперфектних бројева су 6 21 28 301 325 496 697 ... са одговарајућим вредностима к 1 2 1 6 3 1 12 ...
стринг субстринг
Примери:
Input : N = 36 K = 1 Output : 34 is not 1-HyperPerfect Explanation: The Divisors of 36 are 2 3 4 6 9 12 18 the sum of the divisors is 54. For N = 36 to be 1-Hyperperfect it would require 36 = 1 + 1(54) which we see is invalid Input : N = 325 K = 3 Output : 325 is 3-HyperPerfect Explanation: We can use the first condition to evaluate this as K is odd and > 1 so here p = (3*k+1)/2 = 5 q = (3*k+4) = 13 p and q are both prime so we compute p^2 * q = 5 ^ 2 * 13 = 325 Hence N is a valid HyperPerfect numberC++
// C++ 4.3.2 program to check whether a // given number is k-hyperperfect #include using namespace std; // function to find the sum of all // proper divisors (excluding 1 and N) int divisorSum(int N int K) { int sum = 0; // Iterate only until sqrt N as we are // going to generate pairs to produce // divisors for (int i = 2 ; i <= ceil(sqrt(N)) ; i++) // As divisors occur in pairs we can // take the values i and N/i as long // as i divides N if (N % i == 0) sum += ( i + N/i ); return sum; } // Function to check whether the given number // is prime bool isPrime(int n) { //base and corner cases if (n == 1 || n == 0) return false; if (n <= 3) return true; // Since integers can be represented as // some 6*k + y where y >= 0 we can eliminate // all integers that can be expressed in this // form if (n % 2 == 0 || n % 3 == 0) return false; // start from 5 as this is the next prime number for (int i=5; i*i<=n; i=i+6) if (n % i == 0 || n % ( i + 2 ) == 0) return false; return true; } // Returns true if N is a K-Hyperperfect number // Else returns false. bool isHyperPerfect(int N int K) { int sum = divisorSum(N K); // Condition from the definition of hyperperfect if ((1 + K * (sum)) == N) return true; else return false; } // Driver function to test for hyperperfect numbers int main() { int N1 = 1570153 K1 = 12; int N2 = 321 K2 = 3; // First two statements test against the condition // N = 1 + K*(sum(proper divisors)) if (isHyperPerfect(N1 K1)) cout << N1 << ' is ' << K1 <<'-HyperPerfect' << 'n'; else cout << N1 << ' is not ' << K1 <<'-HyperPerfect' << 'n'; if (isHyperPerfect(N2 K2)) cout << N2 << ' is ' << K2 <<'-HyperPerfect' << 'n'; else cout << N2 << ' is not ' << K2 <<'-HyperPerfect' << 'n'; return 0; }
Java // Java program to check // whether a given number // is k-hyperperfect import java.io.*; class GFG { // function to find the // sum of all proper // divisors (excluding // 1 and N) static int divisorSum(int N int K) { int sum = 0; // Iterate only until // sqrt N as we are // going to generate // pairs to produce // divisors for (int i = 2 ; i <= Math.ceil(Math.sqrt(N)); i++) // As divisors occur in // pairs we can take // the values i and N/i // as long as i divides N if (N % i == 0) sum += (i + N / i); return sum; } // Function to check // whether the given // number is prime static boolean isPrime(int n) { // base and corner cases if (n == 1 || n == 0) return false; if (n <= 3) return true; // Since integers can be // represented as some // 6*k + y where y >= 0 // we can eliminate all // integers that can be // expressed in this form if (n % 2 == 0 || n % 3 == 0) return false; // start from 5 as this // is the next prime number for (int i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % ( i + 2 ) == 0) return false; return true; } // Returns true if N is // a K-Hyperperfect number // Else returns false. static boolean isHyperPerfect(int N int K) { int sum = divisorSum(N K); // Condition from the // definition of hyperperfect if ((1 + K * (sum)) == N) return true; else return false; } // Driver Code public static void main (String[] args) { int N1 = 1570153 K1 = 12; int N2 = 321 K2 = 3; // First two statements test // against the condition // N = 1 + K*(sum(proper divisors)) if (isHyperPerfect(N1 K1)) System.out.println (N1 + ' is ' + K1 + '-HyperPerfect' ); else System.out.println(N1 + ' is not ' + K1 + '-HyperPerfect' ); if (isHyperPerfect(N2 K2)) System.out.println( N2 + ' is ' + K2 + '-HyperPerfect' ); else System.out.println(N2 + ' is not ' + K2 + '-HyperPerfect'); } } // This code is contributed by ajit
Python3 # Python3 program to check whether a # given number is k-hyperperfect import math # Function to find the sum of all # proper divisors (excluding 1 and N) def divisorSum(N K): Sum = 0 # Iterate only until sqrt N as we are # going to generate pairs to produce # divisors for i in range(2 math.ceil(math.sqrt(N))): # As divisors occur in pairs we can # take the values i and N/i as long # as i divides N if (N % i == 0): Sum += (i + int(N / i)) return Sum # Function to check whether the given # number is prime def isPrime(n): # Base and corner cases if (n == 1 or n == 0): return False if (n <= 3): return True # Since integers can be represented as # some 6*k + y where y >= 0 we can eliminate # all integers that can be expressed in this # form if (n % 2 == 0 or n % 3 == 0): return False # Start from 5 as this is the next # prime number i = 5 while (i * i <= n): if (n % i == 0 or n % (i + 2) == 0): return False i += 6 return True # Returns true if N is a K-Hyperperfect # number. Else returns false. def isHyperPerfect(N K): Sum = divisorSum(N K) # Condition from the definition # of hyperperfect if ((1 + K * (Sum)) == N): return True else: return False # Driver code N1 = 1570153 K1 = 12 N2 = 321 K2 = 3 # First two statements test against the condition # N = 1 + K*(sum(proper divisors)) if (isHyperPerfect(N1 K1)): print(N1 ' is ' K1 '-HyperPerfect' sep = '') else: print(N1 ' is not ' K1 '-HyperPerfect' sep = '') if (isHyperPerfect(N2 K2)): print(N2 ' is ' K2 '-HyperPerfect' sep = '') else: print(N2 ' is not ' K2 '-HyperPerfect' sep = '') # This code is contributed by avanitrachhadiya2155
C# // C# program to check // whether a given number // is k-hyperperfect using System; class GFG { // function to find the // sum of all proper // divisors (excluding // 1 and N) static int divisorSum(int N int K) { int sum = 0; // Iterate only until // sqrt N as we are // going to generate // pairs to produce // divisors for (int i = 2 ; i <= Math.Ceiling(Math.Sqrt(N)); i++) // As divisors occur in // pairs we can take // the values i and N/i // as long as i divides N if (N % i == 0) sum += (i + N / i); return sum; } // Function to check // whether the given // number is prime static bool isPrime(int n) { // base and corner cases if (n == 1 || n == 0) return false; if (n <= 3) return true; // Since integers can be // represented as some // 6*k + y where y >= 0 // we can eliminate all // integers that can be // expressed in this form if (n % 2 == 0 || n % 3 == 0) return false; // start from 5 as this // is the next prime number for (int i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % ( i + 2 ) == 0) return false; return true; } // Returns true if N is // a K-Hyperperfect number // Else returns false. static bool isHyperPerfect(int N int K) { int sum = divisorSum(N K); // Condition from the // definition of hyperperfect if ((1 + K * (sum)) == N) return true; else return false; } // Driver Code static public void Main () { int N1 = 1570153 K1 = 12; int N2 = 321 K2 = 3; // First two statements // test against the // condition N = 1 + K* // (sum(proper divisors)) if (isHyperPerfect(N1 K1)) Console.WriteLine(N1 + ' is ' + K1 + '-HyperPerfect' ); else Console.WriteLine(N1 + ' is not ' + K1 + '-HyperPerfect' ); if (isHyperPerfect(N2 K2)) Console.WriteLine( N2 + ' is ' + K2 + '-HyperPerfect' ); else Console.WriteLine(N2 + ' is not ' + K2 + '-HyperPerfect'); } } // This code is contributed // by akt_mit
PHP // PHP 4.3.2 program to check // whether a given number is // k-hyperperfect // function to find the sum // of all proper divisors // (excluding 1 and N) function divisorSum($N $K) { $sum = 0; // Iterate only until // sqrt N as we are // going to generate // pairs to produce // divisors for ($i = 2 ; $i <= ceil(sqrt($N)) ; $i++) // As divisors occur in // pairs we can take the // values i and N/i as long // as i divides N if ($N % $i == 0) $sum += ( $i + $N / $i); return $sum; } // Function to check whether // the given number is prime function isPrime($n) { // base and corner cases if ($n == 1 || $n == 0) return false; if ($n <= 3) return true; // Since integers can be // represented as some 6*k + y // where y >= 0 we can // eliminate all integers that // can be expressed in this form if ($n % 2 == 0 || $n % 3 == 0) return false; // start from 5 as this // is the next prime number for ($i = 5; $i * $i <= $n; $i = $i + 6) if ($n % $i == 0 || $n % ($i + 2) == 0) return false; return true; } // Returns true if N is a // K-Hyperperfect number // Else returns false. function isHyperPerfect($N $K) { $sum = divisorSum($N $K); // Condition from the // definition of hyperperfect if ((1 + $K * ($sum)) == $N) return true; else return false; } // Driver Code $N1 = 1570153; $K1 = 12; $N2 = 321; $K2 = 3; // First two statements test // against the condition // N = 1 + K*(sum(proper divisors)) if (isHyperPerfect($N1 $K1)) echo $N1 ' is ' $K1 '-HyperPerfect' 'n'; else echo $N1 ' is not ' $K1 '-HyperPerfect' 'n'; if (isHyperPerfect($N2 $K2)) echo $N2 ' is ' K2 '-HyperPerfect' 'n'; else echo $N2 ' is not ' $K2 '-HyperPerfect' 'n'; // This code is contributed // by akt_mit ?> JavaScript <script> // Javascript program to check // whether a given number // is k-hyperperfect // Function to find the // sum of all proper // divisors (excluding // 1 and N) function divisorSum(N K) { let sum = 0; // Iterate only until sqrt N as // we are going to generate // pairs to produce divisors for(let i = 2; i <= Math.ceil(Math.sqrt(N)); i++) // As divisors occur in // pairs we can take // the values i and N/i // as long as i divides N if (N % i == 0) sum += (i + parseInt(N / i 10)); return sum; } // Function to check // whether the given // number is prime function isPrime(n) { // base and corner cases if (n == 1 || n == 0) return false; if (n <= 3) return true; // Since integers can be // represented as some // 6*k + y where y >= 0 // we can eliminate all // integers that can be // expressed in this form if (n % 2 == 0 || n % 3 == 0) return false; // Start from 5 as this // is the next prime number for(let i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return false; return true; } // Returns true if N is // a K-Hyperperfect number // Else returns false. function isHyperPerfect(N K) { let sum = divisorSum(N K); // Condition from the // definition of hyperperfect if ((1 + K * (sum)) == N) return true; else return false; } // Driver code let N1 = 1570153 K1 = 12; let N2 = 321 K2 = 3; // First two statements // test against the // condition N = 1 + K* // (sum(proper divisors)) if (isHyperPerfect(N1 K1)) document.write(N1 + ' is ' + K1 + '-HyperPerfect' + ''); else document.write(N1 + ' is not ' + K1 + '-HyperPerfect' + ''); if (isHyperPerfect(N2 K2)) document.write(N2 + ' is ' + K2 + '-HyperPerfect' + ''); else document.write(N2 + ' is not ' + K2 + '-HyperPerfect' + ''); // This code is contributed by decode2207 </script>
Излаз:
1570153 is 12-HyperPerfect 321 is not 3-HyperPerfect
Временска сложеност: О(?н)
Помоћни простор: О(1)
С обзиром на к, можемо извршити неколико провера у посебним случајевима да бисмо утврдили да ли је број хиперсавршен:
- Ако К > 1 и К је непаран онда нека п = (3*к+1)/2 и к = 3*к+4 . Ако су п и к прости онда стр2к је к-хиперсавршен
- Ако су п и к различити непарни прости бројеви такав да К(п + к ) = пк - 1 за неку позитивну интегралну вредност К онда пк је к-хиперсавршен
Референца:
хттпс://ен.википедиа.орг/вики/Хиперперфецт_нумбер