求一個數n的因子數和n^2因子數[數論]

正經目錄

• 求一個數的因子數
• • 一、求一個數n的因子數-暴力枚舉法（Osqrt(n)）
  • 二、n平方的因子數-數論
  • 三、HDU1299例題引入

求一個數的因子數

一、求一個數n的因子數-暴力枚舉法（Osqrt(n)）

求一個數的因子數其實不必枚舉1~n 的所有數，比如我求12的所有因子，我枚舉到1時，12可以被1整除，同時我就可以知道另一個數12也是他的因子，同理我枚舉到2時，12可以被2整除，另一個數6也可同時求出……即我們隻需枚舉到3就可以求出所有的因子了。可以發現，求n的所有因子數，我們隻需要枚舉到sqrt(n)即可。代碼如下：

int query(int n)
{
	int ans=0;
	for(int i=1;i*i<=n;i++){
		if(n%i==0)
		{
			ans++;
			if(i*i!=n)
			ans++;
		}
	}
	return ans;
}
           

二、n平方的因子數-數論

唯一分解定理：任何一個正整數都可以素因子分解為

n = p1 e1 * p2e2 * … * prer; （其中pr是< n 的素數因子）

n的因子個數為：（e1+1）* (e2+1) * ……* (er+1)

因為(ab)2=a2 b2 同理可得：

n2 的因子數為：（2 * e1+1） (2 * e2+1) * …… (2 * er+1)

此外埃氏篩法時間複雜度為O(n log(log n))。

步驟：我們先篩選出sqrt(n)内的素數，然後對n進行素因子分解即可求出n2 的因子數，此方法适用于n比較大時。

需要注意的是：當你輸入的n本身就是一個大于你所求的長度的素數，他當然不能被0~sqrt(n)的素因子整除，它的素因式分解就是它本身，或者n有兩個因子，一個在素數表裡，另一個在sqrt(n)外，故最後要特判一下，如果是那麼n的因子數要再乘以1*（2*1+1）=3！

模闆（有詳細注釋）[下面]：

三、HDU1299例題引入

HUD1299

主要就是你輸入n,求出n2 的因子數，然後進行進一步求解答案。

其中1<= n <=109，這個資料再來個平方就是1018 是無法用方法一暴力枚舉的！

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<string>
using namespace std;
#define ll long long int
#define Max_size 40005
int prime[Max_size];//裝素數
bool is_prime[Max_size];//是否素數
int Is_prime(int n)
{
	fill(is_prime,is_prime+n,true);
	is_prime[1]=is_prime[0]=false;
	int c=0;//範圍内素數的個數
	for(int i=2;i<n;i++){
		if(is_prime[i])
		{
			for(int j=i*2;j<n;j+=i)
			is_prime[j]=false;//素數的倍數不是素數
			prime[c++]=i;
		}
	}
	return c;//傳回素數的個數 
} 
int main(void)
{
	int n,t,c;//n的範圍為《=1e9 
	scanf("%d",&t);
	c=Is_prime(4e4);
	int k=0;
	while(t--)
	{
		scanf("%d",&n);
		//求n^2的因子數
		//素因式分解：
		int i=0;
		int ans=1,e=0;
		while(i<c&&n!=1)//i<c 
		{
			e=0;
			while(n%prime[i]==0)
			{
				e++;//素因子的指數 
				n/=prime[i];
			}
			i++;
			ans*=(2*e+1);
		}
		//ans為n^2的因子數
		//printf("%d\n",ans);
		
		if(n>1) ans*=(2*1+1);//别忘了 
		//此時i==c 即此時的n本身就是一個大于Max_size=40005的素數，沒有一個數能整除他 
		
		printf("Scenario #%d:\n",++k);
		if(ans%2==1)
		printf("%d\n\n",ans/2+1);
		else
		printf("%d\n\n",ans/2);
	}
	return 0;
}
           

補充：其實代碼中素因式子分解過程中，我們也可以不用先通過埃氏篩處理出前sqrt(n)的素數，直接枚舉也可以的：

typedef long long LL;
LL get_num(LL x){
    LL ans=1,t;
    for(LL i=2;i*i<=x;++i){
        if(x%i==0){//第一個i一定是素數
            t=0;
            while(x%i==0)t++,x/=i;// 完全篩去 i 因子（i的k次幂），確定下一個得到的 i 是 x 的素因子
            ans*=(1+2*t);
        }
    }
    if(x>1)ans*=3;
    return ans;
}
           

如果是多測試并且n比較大是，還是要用先處理出素數表，再對n進行素因子分解比較快。如果是單測試用例，就用此方法，直接sqrt(n)枚舉每一個素因子出來。

你能確定每次整數除的i就是素數？

還真是，怎麼證明呢？比如12的素因子有2（2*6），3（3 *4）。

12=2X2X3.

12%2=0;12/2/2=3;3%3=0;

還是要看素因子分解定理，故“ 完全篩去 i 因子（i的k次幂）”。不會組織語言，關鍵還是素因子分解定理：n = p1 e1 * p2e2 * … * prer; （其中pr是< n 的素因子）。

再舉個例子，30的素因子為2，3，5。一共有8個因子：1，2，3，5，6，10，15，30。

30/2=15（2是素因子）；15%3=0（3是素因子），15/3=5；5%4！=0（4不是素因子）；5%5=0（5是素因子）；

30=21X31X51 ;