欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

深入分析C語(yǔ)言分解質(zhì)因數(shù)的實(shí)現(xiàn)方法

 更新時(shí)間:2015年08月06日 16:17:07   作者:zinss26914  
這篇文章主要介紹了深入分析C語(yǔ)言分解質(zhì)因數(shù)的實(shí)現(xiàn)方法,作者結(jié)合了ACM題目作為相關(guān)拓展,需要的朋友可以參考下

首先來(lái)看一個(gè)最簡(jiǎn)單的C語(yǔ)言實(shí)現(xiàn)質(zhì)因數(shù)分解的列子:

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

原理&&方法
把一個(gè)合數(shù)分解為若干個(gè)質(zhì)因數(shù)的乘積的形式,即求質(zhì)因數(shù)的過(guò)程叫做分解質(zhì)因數(shù),分解質(zhì)因數(shù)只針對(duì)合數(shù)

求一個(gè)數(shù)分解質(zhì)因數(shù),要從最小的質(zhì)數(shù)除起,一直除到結(jié)果為質(zhì)數(shù)為止。分解質(zhì)因數(shù)的算式的叫短除法,和除法的性質(zhì)差不多,還可以用來(lái)求多個(gè)個(gè)數(shù)的公因式:

以24為例:

2 -- 24

2 -- 12

2 -- 6

3 (3是質(zhì)數(shù),結(jié)束)

得出 24 = 2 × 2 × 2 × 3 = 2^3 * 3


代碼
可先用素?cái)?shù)篩選法,篩選出符合條件的質(zhì)因數(shù),然后for循環(huán)遍歷即可,通過(guò)一道題目來(lái)show一下這部分代碼

題目1

    題目描述: 
    求正整數(shù)N(N>1)的質(zhì)因數(shù)的個(gè)數(shù)。 
    相同的質(zhì)因數(shù)需要重復(fù)計(jì)算。如120=2*2*2*3*5,共有5個(gè)質(zhì)因數(shù)。 
    輸入: 
    可能有多組測(cè)試數(shù)據(jù),每組測(cè)試數(shù)據(jù)的輸入是一個(gè)正整數(shù)N,(1<N<10^9)。 
    輸出: 
    對(duì)于每組數(shù)據(jù),輸出N的質(zhì)因數(shù)的個(gè)數(shù)。 
    樣例輸入: 
    120 
    樣例輸出: 
    5 
    提示: 
    注意:1不是N的質(zhì)因數(shù);若N為質(zhì)數(shù),N是N的質(zhì)因數(shù)。 


ac代碼

   

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

深入理解
我所謂的深入理解,就是通過(guò)4星的題目來(lái)靈活運(yùn)用分解質(zhì)因數(shù)的方法,題目如下

題目2

    題目描述: 
    給定n,a求最大的k,使n!可以被a^k整除但不能被a^(k+1)整除。 
    輸入: 
    兩個(gè)整數(shù)n(2<=n<=1000),a(2<=a<=1000) 
    輸出: 
    一個(gè)整數(shù). 
    樣例輸入: 
    6 10 
    樣例輸出: 
    1 

思路
a^k和n!都可能非常大,甚至超過(guò)long long int的表示范圍,所以也就不能直接用取余操作判斷它們之間是否存在整除關(guān)系,因此我們需要換一種思路,從分解質(zhì)因數(shù)入手,假設(shè)兩個(gè)數(shù)a和b:

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

, 則b除以a可以表示為:

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

若b能被a整除,則 b / a必為整數(shù),且兩個(gè)素?cái)?shù)必護(hù)質(zhì),則我們可以得出如下規(guī)律:

    若a存在質(zhì)因數(shù)px,則b必也存在該質(zhì)因數(shù),且該素因數(shù)在b中對(duì)應(yīng)的冪指數(shù)必不小于在a中的冪指數(shù)


另b = n!, a^k = p1^ke1 * p2^ke2 * ... * pn^ken,因此我們需要確定最大的非負(fù)整數(shù)k即可。要求得該k,我們只需要依次測(cè)試a中每一個(gè)素因數(shù),確定b中該素因數(shù)是a中該素因數(shù)的冪指數(shù)的多少倍即可,所有倍數(shù)中最小的那個(gè)即為我們要求得的k

分析到這里,剩下的工作似乎只是對(duì)a和n!分解質(zhì)因數(shù),但是將n!計(jì)算出來(lái)再分解質(zhì)因數(shù),這樣n!數(shù)值太大??紤]n!中含有素因數(shù)p的個(gè)數(shù),即確定素因數(shù)p對(duì)應(yīng)的冪指數(shù)。我們知道n!包含了從1到n區(qū)間所有整數(shù)的乘積, 這些乘積中每一個(gè)p的倍數(shù)(包括其本身)都對(duì)n!貢獻(xiàn)至少一個(gè)p因子,且我們知道在1到n中p的倍數(shù)共有n/p個(gè)。同理,計(jì)算p^2,p^3,...即可

代碼

   

#include <stdio.h> 
  #include <stdlib.h> 
  #include <string.h> 
    
  #define N 1001 
    
  int prime[N], size; 
    
  /** 
   * 素?cái)?shù)篩選法進(jìn)行預(yù)處理 
   */ 
  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; 
      
    // 預(yù)處理 
    initProcess(); 
    
    while (scanf("%d %d", &n, &a) != EOF) { 
      ansbase = (int *)calloc(size, sizeof(int)); 
      ansnum = (int *)calloc(size, sizeof(int)); 
    
      // 將a分解質(zhì)因數(shù) 
      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 
  ****************************************************************/ 

約數(shù)個(gè)數(shù)定理
對(duì)于一個(gè)大于1的正整數(shù)n可以分解質(zhì)因數(shù):

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

, 則n的正約數(shù)的個(gè)數(shù)為:

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

.其中p1,p2,..pn都是n的質(zhì)因數(shù),a1, a2...an是p1,p2,..pn的指數(shù)

證明
n可以分解質(zhì)因數(shù):n=p1^a1 * p2^a2 * p3^a3 * … * pk^ak,

由約數(shù)定義可知p1^a1的約數(shù)有:p1^0, p1^1, p1^2......p1^a1 ,共(a1+1)個(gè);同理p2^a2的約數(shù)有(a2+1)個(gè)......pk^ak的約數(shù)有(ak+1)個(gè)

故根據(jù)乘法原理:n的約數(shù)的個(gè)數(shù)就是

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

題目3

    題目描述: 
    輸入n個(gè)整數(shù),依次輸出每個(gè)數(shù)的約數(shù)的個(gè)數(shù) 
    輸入: 
    輸入的第一行為N,即數(shù)組的個(gè)數(shù)(N<=1000) 
    接下來(lái)的1行包括N個(gè)整數(shù),其中每個(gè)數(shù)的范圍為(1<=Num<=1000000000) 
    當(dāng)N=0時(shí)輸入結(jié)束。 
    輸出: 
    可能有多組輸入數(shù)據(jù),對(duì)于每組輸入數(shù)據(jù), 
    輸出N行,其中每一行對(duì)應(yīng)上面的一個(gè)數(shù)的約數(shù)的個(gè)數(shù)。 
    樣例輸入: 
    5 
    1 3 4 6 12 
    樣例輸出: 
    1 
    2 
    3 
    4 
    6 


代碼

   

#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 
  ****************************************************************/ 

相關(guān)文章

  • C++ 將文件數(shù)據(jù)一次性加載進(jìn)內(nèi)存實(shí)例代碼

    C++ 將文件數(shù)據(jù)一次性加載進(jìn)內(nèi)存實(shí)例代碼

    這篇文章主要介紹了C++ 將文件數(shù)據(jù)一次性加載進(jìn)內(nèi)存實(shí)例代碼的相關(guān)資料,需要的朋友可以參考下
    2017-05-05
  • C語(yǔ)言實(shí)現(xiàn)動(dòng)態(tài)版通訊錄的示例代碼

    C語(yǔ)言實(shí)現(xiàn)動(dòng)態(tài)版通訊錄的示例代碼

    這篇文章主要為大家詳細(xì)介紹了如何利用C語(yǔ)言實(shí)現(xiàn)一個(gè)簡(jiǎn)單的動(dòng)態(tài)版通訊錄,文中的示例代碼講解詳細(xì),對(duì)我們學(xué)習(xí)C語(yǔ)言有一定幫助,需要的可以參考一下
    2022-08-08
  • C++實(shí)現(xiàn)json形式的Socket傳輸圖片

    C++實(shí)現(xiàn)json形式的Socket傳輸圖片

    這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)json形式的Socket傳輸圖片,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2020-03-03
  • C++?Qt實(shí)現(xiàn)一個(gè)解除文件占用小工具

    C++?Qt實(shí)現(xiàn)一個(gè)解除文件占用小工具

    這篇文章主要為大家詳細(xì)介紹了如何利用C++?Qt實(shí)現(xiàn)一個(gè)解除文件占用小工具,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下
    2023-09-09
  • 深入sizeof的使用詳解

    深入sizeof的使用詳解

    本篇文章是對(duì)sizeof的使用進(jìn)行了詳細(xì)的分析介紹,需要的朋友參考下
    2013-05-05
  • C/C++的全緩沖、行緩沖和無(wú)緩沖

    C/C++的全緩沖、行緩沖和無(wú)緩沖

    這篇文章主要介紹了C/C++的全緩沖、行緩沖和無(wú)緩沖的相關(guān)知識(shí),幫助大家更好的理解和學(xué)習(xí)c/c++,感興趣的朋友可以了解下
    2020-08-08
  • C語(yǔ)言植物大戰(zhàn)數(shù)據(jù)結(jié)構(gòu)堆排序圖文示例

    C語(yǔ)言植物大戰(zhàn)數(shù)據(jù)結(jié)構(gòu)堆排序圖文示例

    這篇文章主要為大家介紹了C語(yǔ)言植物大戰(zhàn)數(shù)據(jù)結(jié)構(gòu)堆排序的圖文示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪
    2022-05-05
  • 詳解C語(yǔ)言之文件操作(上)

    詳解C語(yǔ)言之文件操作(上)

    這篇文章主要介紹了關(guān)于C語(yǔ)言文件操作方法的相關(guān)資料,小編覺(jué)得這篇文章寫(xiě)的還不錯(cuò),需要的朋友可以參考下,希望能夠給你帶來(lái)幫助
    2021-11-11
  • C++超詳細(xì)講解樹(shù)與二叉樹(shù)

    C++超詳細(xì)講解樹(shù)與二叉樹(shù)

    在之前的文章里,我們學(xué)習(xí)的一直是一對(duì)一的線性結(jié)構(gòu),可現(xiàn)實(shí)中,還有很多一對(duì)多的情況需要處理,所以我們需要研究這樣一種一對(duì)多的數(shù)據(jù)結(jié)構(gòu)——樹(shù)
    2022-05-05
  • 數(shù)據(jù)結(jié)構(gòu)之帶頭結(jié)點(diǎn)的單鏈表

    數(shù)據(jù)結(jié)構(gòu)之帶頭結(jié)點(diǎn)的單鏈表

    單鏈表是一種鏈?zhǔn)酱嫒〉臄?shù)據(jù)結(jié)構(gòu),用一組地址任意的存儲(chǔ)單元存放線性表中的數(shù)據(jù)元素。鏈表中的數(shù)據(jù)是以結(jié)點(diǎn)來(lái)表示的,每個(gè)結(jié)點(diǎn)的構(gòu)成:數(shù)據(jù)域(數(shù)據(jù)元素的映象)?+?指針域(指示后繼元素存儲(chǔ)位置),元素就是存儲(chǔ)數(shù)據(jù)的存儲(chǔ)單元,指針就是連接每個(gè)結(jié)點(diǎn)的地址數(shù)據(jù)
    2023-07-07

最新評(píng)論