The realization method of C language decomposition prime factor is deeply analyzed

  • 2020-04-02 03:12:05
  • OfStack

First, let's take a look at the simplest C language to achieve prime factorization:


#include <stdio.h>
void main( )
{
  int data, i = 2;
  scanf("%d", &data);
  while(data > 1)
  {
    if(data % i == 0)
    {
      printf("%d ", i);
      data /= i;
    }
    else i++;
  }
}

Principle && method
The process of finding a prime factor by decomposing a composite into a product of prime factors is called the decomposition of prime factors

To find a prime factor of a number, you divide by the smallest prime number until the result is prime. The formula for resolving prime factors is called short division, which is similar to the property of division. It can also be used to find the common factor of multiple Numbers:

Take 24:

2-24

2-12

2-6

3 (3 is prime, end)

So we get 24 is equal to 2 times 2 times 2 times 3 is equal to 2 to the third times 3


code
We can use the prime number screening method to screen out the prime factors that meet the conditions, and then for loop traversal, through a problem to show this part of the code

Title 1

      Title description:  
      The positive integer N of N > 1) the number of prime factors of.  
      The same prime factors need to be calculated twice. If 120 is 2 times 2 times 2 times 3 times 5, there are 5 prime factors.  
      Input:  
      There may be multiple sets of test data, each set of test data input is a positive integer N, (1 < N < 10 ^ 9).  
      Output:  
      For each set of data, the number of prime factors of N is output.  
      Sample input:  
      120  
      Sample output:  
      5  
      Tip:  
      Note: 1 is not a prime factor of N; If N is prime, N is a prime factor of N.  


Ac code

     


 #include <stdio.h> 
   
  int main() 
  { 
    int n, count, i; 
   
    while (scanf("%d", &n) != EOF) { 
      count = 0; 
   
      for (i = 2; i * i <= n; i ++) { 
        if(n % i == 0) { 
          while (n % i == 0) { 
            count ++; 
            n /= i; 
          } 
        } 
      } 
   
      if (n > 1) { 
        count ++; 
      } 
   
      printf("%dn", count); 
    } 
   
    return 0; 
  } 

Deep understanding of
What I mean by in-depth understanding is that I can flexibly apply the method of prime factor decomposition through the four-star problem, which is as follows

Topic 2

      Title description:  
      Given n, a is the largest k, n factorial. It's divisible by a to the k but not by a to the k plus 1.  
      Input:  
      Two integers n of 2 < = n < = 1000), a (2) < = a < = 1000).  
      Output:  
      An integer.  
      Sample input:  
      6 to 10  
      Sample output:  
      1  

Train of thought
A ^ k and n! Both of them may be very large, even beyond the expression range of long long int, so it is not possible to directly judge whether there is a divisible division relationship between them by the complementary operation. Therefore, we need to change our thinking and start from the decomposition of prime factors, assuming two Numbers a and b:


a = p1^e1 * p2^e2 * ... * pn^en, b = p1^d1 * p2^d2 * ... * pn^dn

, then b divided by a can be expressed as:


b / a = (p1^d1 * p2^d2 * ... * pn^dn) / (p1^e1 * p2^e2 * ... * pn^en)

If b can be divisible by a, then b/a must be an integer, and two prime Numbers must protect the quality, then we can get the following rule:

      If a has a prime factor px, then b must also have the prime factor, and the power of the prime factor in b must be no less than the power in a


The other b = n! A to the k = p1 to the ke1 * p2 to the ke2 *... Times pn to the Ken, so we need to determine the largest non-negative integer k. To find the k, we just need to test each prime factor in a in turn, to determine how many times the prime factor in b is the power of the prime factor in a, and the smallest of all the multiples is the k we want

At this point, the rest of the work seems to be on a and n! I'm going to factor prime, but I'm going to factor n factorial And then factor out the prime factors, so n factorial The number is too large. Considering the n! Contains the number of prime factor p, that is to determine the corresponding power exponent of prime factor p. We know that n factorial Contains the product of all integers from 1 to n, each of which is a multiple of p (including itself) with respect to n! It contributes at least one factor of p, and we know that there are n/p multiples of p from 1 to n. Similarly, calculate p^2, p^3... Can be

code

     


#include <stdio.h> 
  #include <stdlib.h> 
  #include <string.h> 
    
  #define N 1001 
    
  int prime[N], size; 
    
   
  void initProcess() 
  { 
    int i, j; 
      
    for (prime[0] = prime[1] = 0, i = 2; i < N; i ++) { 
      prime[i] = 1; 
    } 
    
    size = 0; 
    
    for (i = 2; i < N; i ++) { 
      if (prime[i]) { 
        size ++; 
        for (j = 2 * i; j < N; j += i) { 
          prime[j] = 0; 
        } 
      } 
    } 
  } 
    
  int main(void) 
  { 
    int i, n, a, k, num, count, base, tmp, *ansbase, *ansnum; 
      
    //pretreatment
    initProcess(); 
    
    while (scanf("%d %d", &n, &a) != EOF) { 
      ansbase = (int *)calloc(size, sizeof(int)); 
      ansnum = (int *)calloc(size, sizeof(int)); 
    
      //I'm going to factor a into prime factors
      for (i = 2, num = 0; i < N && a != 1; i ++) { 
        if (prime[i] && a % i == 0) { 
          ansbase[num] = i; 
          ansnum[num] = 0; 
            
          while (a != 1 && a % i == 0) { 
            ansnum[num] += 1; 
            a = a / i; 
          } 
    
          num ++; 
        } 
      } 
    
      //Find the smallest k
      for (i = 0, k = 0x7fffffff; i < num; i ++) { 
        base = ansbase[i]; 
        count = 0; 
        while (base <= n) { 
          count += n / base; 
          base *= ansbase[i]; 
        } 
    
        tmp = count / ansnum[i]; 
        if (tmp < k) k = tmp; 
      } 
    
      printf("%dn", k);  
    } 
    
    return 0; 
  } 
    
   

The divisor number theorem
For a positive integer n greater than 1, the prime factors can be decomposed:


n = p1^a1 * p2^a2 * p3^a3 * ... * pn^an

, then the number of positive divisor of n is:


 (a1 + 1) * (a2 + 1) * ... *(an + 1)

. The p1, p2,... Pn is a prime factor of n, a1, a2... The an is p1, p2,... The index of the pn

prove
N can be divided into prime factors: n=p1^a1 * p2^a2 * p3^a3 *... * pk ^ ak,

By the definition of divisor, we can see that the divisors of p1 to a1 are :p1 to the 0, p1 to the 1, p1 to the 2...... P1 to the a1, a1 plus 1; Similarly, the divisor of p2 to the a2 is a2+1... Pk to the ak has a divisor of ak plus 1

Therefore, according to the multiplication principle, the number of divisors of n is


(a1+1 ) * ( a2+1 ) * ( a3+1 ) * ... * (ak+1)

Topic 3

      Title description:  
      Input n integers, in turn output the number of divisors of each number  
      Input:  
      The first behavior of the input is N, which is the number of arrays (N) < = 1000).  
      The next 1 line contains N integers, each of which ranges from (1) < Num = < = 1000000000).  
      The input ends when N=0.  
      Output:  
      There may be multiple sets of input data, and for each set of input data,  
      Output N rows, each of which corresponds to the number of divisors of the number above.  
      Sample input:  
      5  
      1, 3, 4, 6, 12  
      Sample output:  
      1  
      2  
      3  
      4  
      6  


code

     


#include <stdio.h> 
  #include <stdlib.h> 
    
  #define N 40000 
    
  typedef long long int lint; 
    
  int prime[N], size; 
    
  void init() 
  { 
    int i, j; 
    
    for (prime[0] = prime[1] = 0, i = 2; i < N; i ++) { 
      prime[i] = 1; 
    } 
      
    size = 0; 
    
    for (i = 2; i < N; i ++) { 
      if (prime[i]) { 
        size ++; 
        for (j = 2 * i; j < N; j += i) 
          prime[j] = 0; 
      } 
    } 
  } 
    
  lint numPrime(int n) 
  { 
    int i, num, *ansnum, *ansprime; 
    lint count; 
    
    ansnum = (int *)malloc(sizeof(int) * (size + 1)); 
    ansprime = (int *)malloc(sizeof(int) * (size + 1)); 
    
    for (i = 2, num = 0; i < N && n != 1; i ++) { 
      if (prime[i] && n % i == 0) { 
        ansprime[num] = i; 
        ansnum[num] = 0; 
        while (n != 1 && n % i == 0) { 
          ansnum[num] += 1; 
          n /= i; 
        } 
        num ++; 
      } 
    } 
    
    if (n != 1) { 
      ansprime[num] = n; 
      ansnum[num] = 1; 
      num ++; 
    } 
    
    for (i = 0, count = 1; i < num; i ++) { 
      count *= (ansnum[i] + 1); 
    } 
    
    free(ansnum); 
    free(ansprime); 
    
    return count; 
  } 
    
    
  int main(void) 
  { 
    int i, n, *arr; 
    lint count; 
    
    init(); 
    
    while (scanf("%d", &n) != EOF && n != 0) { 
      arr = (int *)malloc(sizeof(int) * n); 
      for (i = 0; i < n; i ++) { 
        scanf("%d", arr + i); 
      } 
    
      for (i = 0; i < n; i ++) { 
        count = numPrime(arr[i]); 
        printf("%lldn", count); 
      } 
    
      free(arr); 
    } 
    
    return 0; 
  } 
   


Related articles: