给定一个数字 N ，计算的除数总数 N .
null
例如：
输入： n=4 输出： 8. 说明： 4.24岁。24的除数是1，2，3，4，6， 8、12和24。
输入： n=5 输出： 16 说明： 5.是120。120的除数是1、2、3、4、5、6、8、10、12、15、20、24、30、40、60和12
一个简单的解决方案是首先计算给定数的阶乘，然后计算阶乘的除数。此解决方案效率不高，可能会由于阶乘计算而导致溢出。 更好的解决方案是基于 勒让德公式 .以下是步骤：
- 查找所有小于或等于n（输入数）的素数。我们可以使用 筛选算法 为了这个。让n为6。所有小于6的素数都是{2,3,5}。
- 对于每一个素数，p求其除以n！的最大幂！。我们使用 勒让德公式 为此目的。 除以n的最大幂的值！是⌊不适用⌋ + ⌊n/（p） 2. )⌋ + ⌊n/（p） 3. )⌋ + …… 设这些值为exp1，exp2，exp3，……使用上述公式，我们得到以下n=6的值。
- 2的最大幂除以6！，exp1=4。
- 3的最大幂除以6！，exp2=2。
- 5的最大幂除以6！，exp3=1。
- 结果是（exp1+1）*（exp2+1）*（exp3+1）…对于所有素数，对于n=6，exp1、exp2和exp3的值分别为42和1（在上面的步骤2中计算）。我们的结果是（4+1）*（2+1）*（1+1）=30
下面是上述想法的实施。
C++
// C++ program to find count of divisors in n! #include<bits/stdc++.h> using namespace std; typedef unsigned long long int ull; // allPrimes[] stores all prime numbers less // than or equal to n. vector<ull> allPrimes; // Fills above vector allPrimes[] for a given n void sieve( int n) { // Create a boolean array "prime[0..n]" and // initialize all entries it as true. A value // in prime[i] will finally be false if i is // not a prime, else true. vector< bool > prime(n+1, true ); // Loop to update prime[] for ( int p=2; p*p<=n; p++) { // If prime[p] is not changed, then it // is a prime if (prime[p] == true ) { // Update all multiples of p for ( int i=p*2; i<=n; i += p) prime[i] = false ; } } // Store primes in the vector allPrimes for ( int p=2; p<=n; p++) if (prime[p]) allPrimes.push_back(p); } // Function to find all result of factorial number ull factorialDivisors(ull n) { sieve(n); // create sieve // Initialize result ull result = 1; // find exponents of all primes which divides n // and less than n for ( int i=0; i < allPrimes.size(); i++) { // Current divisor ull p = allPrimes[i]; // Find the highest power (stored in exp)' // of allPrimes[i] that divides n using // Legendre's formula. ull exp = 0; while (p <= n) { exp = exp + (n/p); p = p*allPrimes[i]; } // Multiply exponents of all primes less // than n result = result*( exp +1); } // return total divisors return result; } // Driver code int main() { cout << factorialDivisors(6); return 0; } |
JAVA
// JAVA program to find count of divisors in n! import java.util.*; class GFG { // allPrimes[] stores all prime numbers less // than or equal to n. static Vector<Integer> allPrimes= new Vector<Integer>(); // Fills above vector allPrimes[] for a given n static void sieve( int n){ // Create a boolean array "prime[0..n]" and // initialize all entries it as true. A value // in prime[i] will finally be false if i is // not a prime, else true. boolean []prime= new boolean [n+ 1 ]; for ( int i= 0 ;i<=n;i++) prime[i]= true ; // Loop to update prime[] for ( int p= 2 ; p*p<=n; p++) { // If prime[p] is not changed, then it // is a prime if (prime[p] == true ) { // Update all multiples of p for ( int i=p* 2 ; i<=n; i += p) prime[i] = false ; } } // Store primes in the vector allPrimes for ( int p= 2 ; p<=n; p++) if (prime[p]) allPrimes.add(p); } // Function to find all result of factorial number static long factorialDivisors( int n) { sieve(n); // create sieve // Initialize result long result = 1 ; // find exponents of all primes which divides n // and less than n for ( int i= 0 ; i < allPrimes.size(); i++) { // Current divisor long p = allPrimes.get(i); // Find the highest power (stored in exp)' // of allPrimes[i] that divides n using // Legendre's formula. long exp = 0 ; while (p <= n) { exp = exp + (n/p); p = p*allPrimes.get(i); } // Multiply exponents of all primes less // than n result = result*(exp+ 1 ); } // return total divisors return result; } // Driver code public static void main(String []args) { System.out.println(factorialDivisors( 6 )); } } //This code is contributed by ihritik |
Python3
# Python3 program to find count # of divisors in n! # allPrimes[] stores all prime # numbers less than or equal to n. allPrimes = []; # Fills above vector allPrimes[] # for a given n def sieve(n): # Create a boolean array "prime[0..n]" # and initialize all entries it as true. # A value in prime[i] will finally be # false if i is not a prime, else true. prime = [ True ] * (n + 1 ); # Loop to update prime[] p = 2 ; while (p * p < = n): # If prime[p] is not changed, # then it is a prime if (prime[p] = = True ): # Update all multiples of p i = p * 2 ; while (i < = n): prime[i] = False ; i + = p; p + = 1 ; # Store primes in the vector allPrimes for p in range ( 2 , n + 1 ): if (prime[p]): allPrimes.append(p); # Function to find all result of # factorial number def factorialDivisors(n): sieve(n); # create sieve # Initialize result result = 1 ; # find exponents of all primes # which divides n and less than n for i in range ( len (allPrimes)): # Current divisor p = allPrimes[i]; # Find the highest power (stored in exp)' # of allPrimes[i] that divides n using # Legendre's formula. exp = 0 ; while (p < = n): exp = exp + int (n / p); p = p * allPrimes[i]; # Multiply exponents of all # primes less than n result = result * (exp + 1 ); # return total divisors return result; # Driver Code print (factorialDivisors( 6 )); # This code is contributed by mits |
C#
// C# program to find count of divisors in n! using System; using System.Collections; class GFG { // allPrimes[] stores all prime numbers less // than or equal to n. static ArrayList allPrimes = new ArrayList(); // Fills above vector allPrimes[] for a given n static void sieve( int n) { // Create a boolean array "prime[0..n]" and // initialize all entries it as true. A value // in prime[i] will finally be false if i is // not a prime, else true. bool [] prime = new bool [n+1]; for ( int i = 0; i <= n; i++) prime[i] = true ; // Loop to update prime[] for ( int p = 2; p * p <= n; p++) { // If prime[p] is not changed, then it // is a prime if (prime[p] == true ) { // Update all multiples of p for ( int i = p*2; i <= n; i += p) prime[i] = false ; } } // Store primes in the vector allPrimes for ( int p = 2; p <= n; p++) if (prime[p]) allPrimes.Add(p); } // Function to find all result of factorial number static int factorialDivisors( int n) { sieve(n); // create sieve // Initialize result int result = 1; // find exponents of all primes which divides n // and less than n for ( int i = 0; i < allPrimes.Count; i++) { // Current divisor int p = ( int )allPrimes[i]; // Find the highest power (stored in exp)' // of allPrimes[i] that divides n using // Legendre's formula. int exp = 0; while (p <= n) { exp = exp + (n / p); p = p * ( int )allPrimes[i]; } // Multiply exponents of all primes less // than n result = result * (exp + 1); } // return total divisors return result; } // Driver code public static void Main() { Console.WriteLine(factorialDivisors(6)); } } //This code is contributed by chandan_jnu |
PHP
<?php // PHP program to find count of // divisors in n! // allPrimes[] stores all prime numbers // less than or equal to n. $allPrimes = array (); // Fills above vector allPrimes[] // for a given n function sieve( $n ) { global $allPrimes ; // Create a boolean array "prime[0..n]" and // initialize all entries it as true. A value // in prime[i] will finally be false if i is // not a prime, else true. $prime = array_fill (0, $n + 1, true); // Loop to update prime[] for ( $p = 2; $p * $p <= $n ; $p ++) { // If prime[p] is not changed, // then it is a prime if ( $prime [ $p ] == true) { // Update all multiples of p for ( $i = $p * 2; $i <= $n ; $i += $p ) $prime [ $i ] = false; } } // Store primes in the vector allPrimes for ( $p = 2; $p <= $n ; $p ++) if ( $prime [ $p ]) array_push ( $allPrimes , $p ); } // Function to find all result // of factorial number function factorialDivisors( $n ) { global $allPrimes ; sieve( $n ); // create sieve // Initialize result $result = 1; // find exponents of all primes // which divides n and less than n for ( $i = 0; $i < count ( $allPrimes ); $i ++) { // Current divisor $p = $allPrimes [ $i ]; // Find the highest power (stored in exp) // of allPrimes[i] that divides n using // Legendre's formula. $exp = 0; while ( $p <= $n ) { $exp = $exp + (int)( $n / $p ); $p = $p * $allPrimes [ $i ]; } // Multiply exponents of all primes // less than n $result = $result * ( $exp + 1); } // return total divisors return $result ; } // Driver Code echo factorialDivisors(6); // This code is contributed by mits ?> |
Javascript
<script> // JavaScript program to find count of divisors in n! // allPrimes[] stores all prime numbers less // than or equal to n. let allPrimes = []; // Fills above vector allPrimes[] for a given n function sieve(n) { // Create a boolean array "prime[0..n]" and // initialize all entries it as true. A value // in prime[i] will finally be false if i is // not a prime, else true. let prime = new Array(n+1); for (let i = 0; i <= n; i++) prime[i] = true ; // Loop to update prime[] for (let p = 2; p * p <= n; p++) { // If prime[p] is not changed, then it // is a prime if (prime[p] == true ) { // Update all multiples of p for (let i = p*2; i <= n; i += p) prime[i] = false ; } } // Store primes in the vector allPrimes for (let p = 2; p <= n; p++) if (prime[p]) allPrimes.push(p); } // Function to find all result of factorial number function factorialDivisors(n) { sieve(n); // create sieve // Initialize result let result = 1; // find exponents of all primes which divides n // and less than n for (let i = 0; i < allPrimes.length; i++) { // Current divisor let p = allPrimes[i]; // Find the highest power (stored in exp)' // of allPrimes[i] that divides n using // Legendre's formula. let exp = 0; while (p <= n) { exp = exp + parseInt(n / p, 10); p = p * allPrimes[i]; } // Multiply exponents of all primes less // than n result = result * (exp + 1); } // return total divisors return result; } document.write(factorialDivisors(6)); </script> |
输出
30
本文由 沙申克·米什拉（古卢） .本文由Geeksforgeks团队审阅。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
