1 素?cái)?shù)

1.1 素?cái)?shù)的判斷

素?cái)?shù)的判斷較為簡單，直接上代碼，需要注意的幾點(diǎn)：

bool isPrime(int n){if(n==1) return false; //1需要特判int sqr=(int)sqrt(n*1.0); //之所以要用這條語句而不是在for循環(huán)里使用sqrt(n)，解釋如下for(int i=2;i<=sqr;i++){if(n%i==0) return false;}return true; }

在上面的代碼中，其中需要用到一條? int sqr=(int)sqrt(n*1.0); 用來在循環(huán)中做一個(gè)循環(huán)邊界呢。首先可以從 double sqrt(double) 可以看出，sqrt()的返回值和參數(shù)都是double類型的。在計(jì)算機(jī)中，小數(shù)都是不精確的，如，sqrt(9)是等于3.000000000001還是2.999999999999都是不好講的。有的計(jì)算機(jī)可能給出前者，有的則可能是后者，這樣對(duì)我們循環(huán)的邊界的判斷造成了影響。于是就用到了上面一行代碼，轉(zhuǎn)化參數(shù)的數(shù)據(jù)類型，保證sqrt得到我們想要的值。

1.2 素?cái)?shù)表的獲取?

下面給出兩個(gè)方法。

首先是比較常用的，對(duì)n不超過是可以的，復(fù)雜度包括了判斷是否為素?cái)?shù)O()和遍歷從1到n的復(fù)雜度O(n)，因此第一種方式（對(duì)n不超過）的時(shí)間復(fù)雜度為O(n) 。下面給出代碼：

const int maxn=101; int Prime[maxn],pNum=0; //數(shù)組Prime()存放所有的素?cái)?shù)，pNum為素?cái)?shù)的個(gè)數(shù) bool p[maxn]={0}; void Find_Prime(){for(int i=1;i<maxn;i++){if(isPrime(i)==true){ //判斷是否為素?cái)?shù)Prime[pNum++]=i;p[i]=true;}} }

其次是時(shí)間復(fù)雜度更小的一種方式，為O()，這是一種什么原理的，我們來看：

2是素?cái)?shù)，因此去掉所有2的倍數(shù)，如4,6,8,10,12,14,16,18,20；

3沒有被前面的步驟篩去，所以3是素?cái)?shù)，因此去掉所有3的倍數(shù)，如6,9,12,15,18；

4被前面的步驟篩去了，所以4不是素?cái)?shù)；

5沒有被前面的步驟篩去，所以5是素?cái)?shù)，因此去掉所有5的倍數(shù)，如5,10,15,20；

6被前面的步驟篩去了，所以6不是素?cái)?shù)；?

……

由上面可以看出，當(dāng)從小到大達(dá)到達(dá)到某數(shù)n的時(shí)候，如果n沒有被前面的步驟篩去，那么n就一定是素?cái)?shù)。原理是：當(dāng)n不是素?cái)?shù)時(shí)，必然有小于n的質(zhì)因數(shù)，這樣在之前篩去質(zhì)因數(shù)的倍數(shù)的時(shí)候就應(yīng)該把n篩去了。所以，當(dāng)n沒有被前面步驟篩去的時(shí)候，就一定是一個(gè)素?cái)?shù)。于是可以給出如下代碼：

const int maxn=101; int Prime[maxn],pNum; //同樣的道理，建立一個(gè)數(shù)組Prime來存放素?cái)?shù)，pNum為蘇數(shù)的個(gè)數(shù) bool p[maxn]={0}; //素?cái)?shù)為0，非素?cái)?shù)為1 void Find_Prime(int n){for(int i=2;i<max;i++){if(p[i]==0){Prime[pNum++]=i;for(int j=i;j<maxn;j += i){p[j]=true;}}} }

2 質(zhì)因數(shù)的分解

質(zhì)因數(shù)分解就是將一個(gè)整數(shù)n分解成若干個(gè)素?cái)?shù)乘積的形式，如8=222，18=2233等等。素?cái)?shù)的尋找上面已經(jīng)講過了，而且值得注意的是2357111317192329的積就已經(jīng)超過了int型的上限了。

我們對(duì)于質(zhì)因數(shù)的分解，不妨先設(shè)一個(gè)結(jié)構(gòu)體：

struct factor{int x,cnt; //x代表了質(zhì)因數(shù)，cnt代表了該質(zhì)因數(shù)的個(gè)數(shù) }fac[10];

那么對(duì)于180來說，就有

fac[0].x=2; fac[0].cnt=2;fac[1].x=3; fac[1].cnt=2;fac[2].x=5; fac[2].cnt=1;

?首先枚舉1~sqrt(n)范圍內(nèi)所有質(zhì)因子p，判斷p是否為n的質(zhì)因數(shù)。

const num=0; void Find_Factor(int n){for(int i=0;i<10;i++){if(n%Prime[i]==0){fac[num].x=Prime[i];fac[num].cnt=0;while(n%fac[num].x==0){fac[num].cnt++;n=n/fac[num].x;}num++;}} }

?如果在上邊步驟結(jié)束后n人大于1，說明n有且僅有一個(gè)質(zhì)因子（即n本身），這時(shí)需要將這個(gè)質(zhì)因子加入fac數(shù)組，令其個(gè)數(shù)為1.

if(n!=1){fac[num].x=n;fac[num++].cnt=1; }

?解釋完畢

總結(jié)

以上是生活随笔為你收集整理的【PAT笔记】数学问题——素数和质因数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。