给定一个正整数n（1<=n<=10 18 ).检查一个数字是否正好有三个不同的因子。“打印” 对 “如果不是这样” 不 “.
null
例如：
Input : 9Output: YesExplanationNumber 9 has exactly three factors:1, 3, 9, hence answer is 'Yes'Input : 10Output : No
简单方法 就是通过使用这种方法生成一个数的所有除数来计算因子，然后检查所有因子的计数是否等于“3”。该方法的时间复杂度为O（sqrt（n））。
更好的方法 就是使用 数论 .根据完美正方形的性质，“ 每个完美正方形（x） 2. )总是只有奇数个因子 “.
如果给定数字的平方根（比如x 2. )是素数（在确定该数为完美平方后），则它必须正好有三个不同的因子，即：。，
- 一个数字 1. 当然
- 一个数字的平方根，即。， 十、 （质数）。
- 编号本身，即。， 十、 2. .
以下是上述方法的实施情况：
C++
// C++ program to check whether number // has exactly three distinct factors // or not #include <bits/stdc++.h> using namespace std; // Utility function to check whether a // number is prime or not bool isPrime( int n) { // Corner cases if (n <= 1) return false ; if (n <= 3) return true ; // This is checked so that we can skip // middle five numbers in below loop if (n % 2 == 0 || n % 3 == 0) return false ; for ( int i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return false ; return true ; } // Function to check whether given number // has three distinct factors or not bool isThreeDisctFactors( long long n) { // Find square root of number int sq = ( int ) sqrt (n); // Check whether number is perfect // square or not if (1LL * sq * sq != n) return false ; // If number is perfect square, check // whether square root is prime or // not return isPrime(sq) ? true : false ; } // Driver program int main() { long long num = 9; if (isThreeDisctFactors(num)) cout << "Yes" ; else cout << "No" ; num = 15; if (isThreeDisctFactors(num)) cout << "Yes" ; else cout << "No" ; num = 12397923568441; if (isThreeDisctFactors(num)) cout << "Yes" ; else cout << "No" ; return 0; } |
JAVA
// Java program to check whether number // has exactly three distinct factors // or not public class GFG { // Utility function to check whether a // number is prime or not static boolean isPrime( int n) { // Corner cases if (n <= 1 ) return false ; if (n <= 3 ) return true ; // This is checked so that we can skip // middle five numbers in below loop if (n % 2 == 0 || n % 3 == 0 ) return false ; for ( int i = 5 ; i * i <= n; i = i + 6 ) if (n % i == 0 || n % (i + 2 ) == 0 ) return false ; return true ; } // Function to check whether given number // has three distinct factors or not static boolean isThreeDisctFactors( long n) { // Find square root of number int sq = ( int )Math.sqrt(n); // Check whether number is perfect // square or not if (1L * sq * sq != n) return false ; // If number is perfect square, check // whether square root is prime or // not return isPrime(sq) ? true : false ; } // Driver program public static void main(String[] args) { long num = 9 ; if (isThreeDisctFactors(num)) System.out.println( "Yes" ); else System.out.println( "No" ); num = 15 ; if (isThreeDisctFactors(num)) System.out.println( "Yes" ); else System.out.println( "No" ); num = 12397923568441L; if (isThreeDisctFactors(num)) System.out.println( "Yes" ); else System.out.println( "No" ); } } |
Python3
# Python 3 program to check whether number # has exactly three distinct factors # or not from math import sqrt # Utility function to check whether a # number is prime or not def isPrime(n): # Corner cases if (n < = 1 ): return False if (n < = 3 ): return True # This is checked so that we can skip # middle five numbers in below loop if (n % 2 = = 0 or n % 3 = = 0 ): return False k = int (sqrt(n)) + 1 for i in range ( 5 ,k, 6 ): if (n % i = = 0 or n % (i + 2 ) = = 0 ): return False return True # Function to check whether given number # has three distinct factors or not def isThreeDisctFactors(n): # Find square root of number sq = int (sqrt(n)) # Check whether number is perfect # square or not if ( 1 * sq * sq ! = n): return False # If number is perfect square, check # whether square root is prime or # not if (isPrime(sq)): return True else : return False # Driver program if __name__ = = '__main__' : num = 9 if (isThreeDisctFactors(num)): print ( "Yes" ) else : print ( "No" ) num = 15 if (isThreeDisctFactors(num)): print ( "Yes" ) else : print ( "No" ) num = 12397923568441 if (isThreeDisctFactors(num)): print ( "Yes" ) else : print ( "No" ) # This code is contributed by # Surendra_Gangwar |
C#
// C# program to check whether number // has exactly three distinct factors // or not using System; public class GFG { // Utility function to check whether // a number is prime or not static bool isPrime( int n) { // Corner cases if (n <= 1) return false ; if (n <= 3) return true ; // This is checked so that we can // skip middle five numbers in // below loop if (n % 2 == 0 || n % 3 == 0) return false ; for ( int i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return false ; return true ; } // Function to check whether given number // has three distinct factors or not static bool isThreeDisctFactors( long n) { // Find square root of number int sq = ( int )Math.Sqrt(n); // Check whether number is perfect // square or not if (1LL * sq * sq != n) return false ; // If number is perfect square, check // whether square root is prime or // not return isPrime(sq) ? true : false ; } // Driver program static public void Main() { long num = 9; if (isThreeDisctFactors(num)) Console.WriteLine( "Yes" ); else Console.WriteLine( "No" ); num = 15; if (isThreeDisctFactors(num)) Console.WriteLine( "Yes" ); else Console.WriteLine( "No" ); num = 12397923568441; if (isThreeDisctFactors(num)) Console.WriteLine( "Yes" ); else Console.WriteLine( "No" ); } } // This Code is contributed by vt_m. |
PHP
<?php // PHP program to check whether // number has exactly three // distinct factors or not // Utility function to check // whether a number is prime // or not function isPrime( $n ) { // Corner cases if ( $n <= 1) return false; if ( $n <= 3) return true; // This is checked so that // we can skip middle five // numbers in below loop if ( $n % 2 == 0 || $n % 3 == 0) return false; for ( $i = 5; $i * $i <= $n ; $i = $i + 6) if ( $n % $i == 0 || $n % ( $i + 2) == 0) return false; return true; } // Function to check // whether given number // has three distinct // factors or not function isThreeDisctFactors( $n ) { // Find square root of number $sq = sqrt( $n ); // Check whether number is // perfect square or not if ( $sq * $sq != $n ) return false; // If number is perfect square, // check whether square root is // prime or not return isPrime( $sq ) ? true : false; } // Driver Code $num = 9; if (isThreeDisctFactors( $num )) echo "Yes" ; else echo "No" ; $num = 15; if (isThreeDisctFactors( $num )) echo "Yes" ; else echo "No" ; $num = 12397923568441; if (isThreeDisctFactors( $num )) echo "Yes" ; else echo "No" ; // This code is contributed by ak_t ?> |
Javascript
<script> // Javascript program to check whether // number has exactly three distinct // factors or not // Utility function to check whether a // number is prime or not function isPrime(n) { // Corner cases if (n <= 1) return false ; if (n <= 3) return true ; // This is checked so that we can skip // middle five numbers in below loop if (n % 2 == 0 || n % 3 == 0) return false ; for (let i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return false ; return true ; } // Function to check whether given number // has three distinct factors or not function isThreeDisctFactors(n) { // Find square root of number let sq = parseInt(Math.sqrt(n)); // Check whether number is perfect // square or not if (sq * sq != n) return false ; // If number is perfect square, check // whether square root is prime or // not return isPrime(sq) ? true : false ; } // Driver code let num = 9; if (isThreeDisctFactors(num)) document.write( "Yes<br>" ); else document.write( "No<br>" ); num = 15; if (isThreeDisctFactors(num)) document.write( "Yes<br>" ); else document.write( "No<br>" ); num = 12397923568441; if (isThreeDisctFactors(num)) document.write( "Yes<br>" ); else document.write( "No<br>" ); // This code is contributed by souravmahato348 </script> |
输出：
YesNoNo
时间复杂性： O（n） 1/4 ) 辅助空间： O（1）
本文由 Shubham Bansal .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客-
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
