深入分析C语言分解质因数的实现方法

#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++;
  }
}

 #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("%d\n", count); 
    } 
   
    return 0; 
  } 

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

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

#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; 
      
    // 预处理 
    initProcess(); 
    
    while (scanf("%d %d", &n, &a) != EOF) { 
      ansbase = (int *)calloc(size, sizeof(int)); 
      ansnum = (int *)calloc(size, sizeof(int)); 
    
      // 将a分解质因数 
      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 ++; 
        } 
      } 
    
      // 求最小的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("%d\n", k);  
    } 
    
    return 0; 
  } 
    
  /************************************************************** 
    Problem: 1104 
    User: wangzhengyi 
    Language: C 
    Result: Accepted 
    Time:0 ms 
    Memory:916 kb 
  ****************************************************************/ 

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

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

(a1+1）*（a2+1）*（a3+1）*…* (ak+1)

#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("%lld\n", count); 
      } 
    
      free(arr); 
    } 
    
    return 0; 
  } 
  /************************************************************** 
    Problem: 1087 
    User: wangzhengyi 
    Language: C 
    Result: Accepted 
    Time:190 ms 
    Memory:1068 kb 
  ****************************************************************/