给定一个数n，求出有序素数签名，并用它求出给定n的除数。 任何正整数，“n”都可以用其素因子的形式表示。如果n有p 1. P 2. ，等作为其主要因子，那么n可以表示为： 
现在，将得到的n的素因子指数按非降序排列。由此获得的安排称为 有序素数签名 正整数n的。 例子：
null
Input : n = 20Output : The Ordered Prime Signature of 20 is : { 1, 2 }The total number of divisors of 20 is 6Input : n = 13Output : The Ordered Prime Signature of 13 is : { 1 }The total number of divisors of 13 is 2
说明：
-
20={1，2}的序素数签名 -
37={1}的序素数签名 -
49={2}的序素数签名
从上面的讨论可以确定，1的素签名是{1}。此外，所有素数都有相同的签名，即{1}，而一个数的素数签名，即素数的k次方（例如，25是5的2次方），总是{k}。 例如：
100={2，2}的有序素数签名，如100=2^2×5^2 现在每个元素加一就得到{3，3}，乘积是3×3=9， i、 100的除数总数是9。 他们是1，2，4，5，10，20，25，50，100。
方法： 1） 求这个数的素数分解 2） 将与素因子对应的每个指数存储在向量中 3） 按升序对向量排序 4） 向向量中的每个元素添加一个 5） 将所有元素相乘
C++
// CPP to find total number of divisors of a // number, using ordered prime signature #include <bits/stdc++.h> using namespace std; // Finding primes upto entered number vector< int > primes( int n) { bool prime[n + 1]; // Finding primes by Sieve // of Eratosthenes method memset (prime, true , sizeof (prime)); for ( int i = 2; i * i <= n; i++) { // If prime[i] is not changed, // then it is prime if (prime[i] == true ) { // Update all multiples of p for ( int j = i * 2; j <= n; j += i) prime[j] = false ; } } vector< int > arr; // Forming array of the prime numbers found for ( int i = 2; i <= n; i++) { if (prime[i]) arr.push_back(i); } return arr; } // Finding ordered prime signature of the number vector< int > signature( int n) { vector< int > r = primes(n); // Map to store prime factors and // the related exponents map< int , int > factor; // Declaring an iterator for map map< int , int >::iterator it; vector< int > sort_exp; int k, t = n; it = factor.begin(); // Finding prime factorization of the number for ( int i = 0; i < r.size(); i++) { if (n % r[i] == 0) { k = 0; while (n % r[i] == 0) { n = n / r[i]; k++; } // Storing the prime factor and // its exponent in map factor.insert(it, pair< int , int >(r[i], k)); // Storing the exponent in a vector sort_exp.push_back(k); } } // Sorting the stored exponents sort(sort_exp.begin(), sort_exp.end()); // Printing the prime signature cout << " The Ordered Prime Signature of " << t << " is : { " ; for ( int i = 0; i < sort_exp.size(); i++) { if (i != sort_exp.size() - 1) cout << sort_exp[i] << ", " ; else cout << sort_exp[i] << " }" ; } return sort_exp; } // Finding total number of divisors of the number void divisors( int n) { int f = 1, l; vector< int > div = signature(n); l = div .size(); // Adding one to each element present for ( int i = 0; i < l; i++) { // in ordered prime signature div [i] += 1; // Multiplying the elements f *= div [i]; } cout << "The total number of divisors of " << n << " is " << f << "" ; } // Driver Method int main() { int n = 13; divisors(n); return 0; } |
JAVA
// JAVA to find total number of divisors of a // number, using ordered prime signature import java.util.*; class GFG { static class pair { int first, second; public pair( int first, int second) { this .first = first; this .second = second; } } // Finding primes upto entered number static Vector<Integer> primes( int n) { boolean []prime = new boolean [n + 1 ]; // Finding primes by Sieve // of Eratosthenes method Arrays.fill(prime, true ); for ( int i = 2 ; i * i <= n; i++) { // If prime[i] is not changed, // then it is prime if (prime[i] == true ) { // Update all multiples of p for ( int j = i * 2 ; j <= n; j += i) prime[j] = false ; } } Vector<Integer> arr = new Vector<>(); // Forming array of the prime numbers found for ( int i = 2 ; i <= n; i++) { if (prime[i]) arr.add(i); } return arr; } // Finding ordered prime signature of the number static Vector<Integer> signature( int n) { Vector<Integer> r = primes(n); // Map to store prime factors and // the related exponents HashMap<Integer,Integer> factor = new HashMap<>(); // Declaring an iterator for map // HashMap<Integer,Integer>::iterator it; Vector<Integer> sort_exp = new Vector<>(); int k, t = n; int it = 0 ; // Finding prime factorization of the number for ( int i = 0 ; i < r.size(); i++) { if (n % r.get(i) == 0 ) { k = 0 ; while (n % r.get(i) == 0 ) { n = n / r.get(i); k++; } // Storing the prime factor and // its exponent in map factor.put(r.get(i), k); // Storing the exponent in a vector sort_exp.add(k); } } // Sorting the stored exponents Collections.sort(sort_exp); // Printing the prime signature System.out.print( " The Ordered Prime Signature of " + t+ " is : { " ); for ( int i = 0 ; i < sort_exp.size(); i++) { if (i != sort_exp.size() - 1 ) System.out.print(sort_exp.get(i) + ", " ); else System.out.print(sort_exp.get(i) + " }" ); } return sort_exp; } // Finding total number of divisors of the number static void divisors( int n) { int f = 1 , l; Vector<Integer> div = signature(n); l = div.size(); // Adding one to each element present for ( int i = 0 ; i < l; i++) { // in ordered prime signature //div[i] += 1; // Multiplying the elements f *= (div.get(i) + 1 ); } System.out.print( "The total number of divisors of " + n + " is " + f + "" ); } // Driver code public static void main(String[] args) { int n = 13 ; divisors(n); } } // This code is contributed by aashish1995 |
C#
// C# to find total number // of divisors of a number, // using ordered prime signature using System; using System.Collections.Generic; class GFG { // Finding primes // upto entered number static List< int > primes( int n) { bool []prime = new bool [n + 1]; // Finding primes by Sieve // of Eratosthenes method for ( int i = 0; i < n + 1; i++) prime[i] = true ; for ( int i = 2; i * i <= n; i++) { // If prime[i] is not // changed, then it is prime if (prime[i] == true ) { // Update all multiples of p for ( int j = i * 2; j <= n; j += i) prime[j] = false ; } } List< int > arr = new List< int >(); // Forming array of the // prime numbers found for ( int i = 2; i <= n; i++) { if (prime[i]) arr.Add(i); } return arr; } // Finding ordered prime // signature of the number static List< int > signature( int n) { List< int > r = primes(n); // Map to store prime factors // and the related exponents var factor = new Dictionary< int , int >(); List< int > sort_exp = new List< int >(); int k, t = n; // Finding prime factorization // of the number for ( int i = 0; i < r.Count; i++) { if (n % r[i] == 0) { k = 0; while (n % r[i] == 0) { n = n / r[i]; k++; } // Storing the prime factor // and its exponent in map factor.Add(r[i], k); // Storing the exponent // in a List sort_exp.Add(k); } } // Sorting the // stored exponents sort_exp.Sort(); // Printing the // prime signature Console.Write( " The Ordered Prime Signature of " + t + " is : { " ); for ( int i = 0; i < sort_exp.Count; i++) { if (i != sort_exp.Count - 1) Console.Write(sort_exp[i] + ", " ); else Console.Write(sort_exp[i] + " }" ); } return sort_exp; } // Finding total number // of divisors of the number static void divisors( int n) { int f = 1, l; List< int > div = signature(n); l = div.Count; // Adding one to each // element present for ( int i = 0; i < l; i++) { // in ordered // prime signature div[i] += 1; // Multiplying // the elements f *= div[i]; } Console.Write( "The total number of divisors of " + n + " is " + f + "" ); } // Driver Code static void Main() { int n = 13; divisors(n); } } // This code is contributed by // Manish Shaw(manishshaw1) |
输出：
The Ordered Prime Signature of 13 is : { 1 }The total number of divisors of 13 is 2
申请： 求一个数的有序素数签名在求除数方面很有用。事实上，一个数的除数总数可以从该数的有序素数签名中推断出来。要实现这一点，只需将一个元素添加到有序素数签名中的每个元素，然后将这些元素相乘。由此得到的乘积给出了该数的除数总数（包括1和该数本身）。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
