Brstjjy

因数（又称约数)是一个常见的数学名词，用于描述非零整数 a{displaystyle a} 和整数 b{displaystyle b} 之间存在的整除关系，即 b{displaystyle b} 可以被 a{displaystyle a} 整除。这里我们称 b{displaystyle b} 是 a{displaystyle a} 的倍数，a{displaystyle a} 是 b{displaystyle b} 的因数、约数或因子.

定义

设 a,b{displaystyle a,b} 满足 a∈N∗,b∈N{displaystyle ain mathbb {N} ^{*},bin mathbb {N} }. 若存在 q∈N{displaystyle qin mathbb {N} } 使得 b=aq{displaystyle b=aq}, 那么就说 b{displaystyle b} 是 a{displaystyle a} 的倍数， a{displaystyle a} 是 b{displaystyle b} 的约数。这种关系记作 a|b{displaystyle a|b},读作“a{displaystyle a} 整除 b{displaystyle b}”.

例如 24=3×8,1150=25×46{displaystyle 24=3times 8,;1150=25times 46}. 所以 3|24,25|1150{displaystyle 3|24,;25|1150}，同时 3{displaystyle 3} 是 24{displaystyle 24} 的因数；25{displaystyle 25} 是 1150{displaystyle 1150} 的因数。

性质

• 若 a|b,b|c{displaystyle a|b,;b|c} 那么 a|c{displaystyle a|c}.

• 若 a|b,a|c{displaystyle a|b,;a|c} 且 x,y∈Z{displaystyle x,yin mathbb {Z} }, 有 a|(bx+cy){displaystyle a|(bx+cy)}.

• 若 a|b{displaystyle a|b}, 设 t≠0{displaystyle tnot =0}, 那么 (ta)|(tb){displaystyle (ta)|(tb)}.

• 若 b=qd+c{displaystyle b=qd+c}, 那么 d|b{displaystyle d|b} 的充要条件是 d|c{displaystyle d|c}
  

• 若 x,y∈Z{displaystyle x,yin mathbb {Z} } 满足 ax+by=1,a|n.b|n{displaystyle ax+by=1,;a|n.;b|n} 那么 ab|n{displaystyle ab|n}.

这里对最后一条性质进行证明:

∵a|n,b|n∴ab|bn,ab|an∴ab|(anx+bny){displaystyle because a|n,;b|nquad therefore ab|bn,;ab|anquad therefore ab|(anx+bny)}

∵ax+by=1∴ab|n{displaystyle because ax+by=1quad therefore ab|n}

证毕。

相关定理

整数的唯一分解定理

任何一个正整数都有且仅有一种方式写出它所有素数因子的乘积表达式。这个过程称为质因数分解

如果 A∈N+{displaystyle Ain mathbb {N} ^{+}}, 那么

A=∏i=1npiai{displaystyle A=prod _{i=1}^{n}p_{i}^{a_{i}}}, 其中 pi{displaystyle p_{i}} 是一个素数.

这种表示方法是唯一的。

因数个数

自然数 N{displaystyle N} 的因数个数以 d(n){displaystyle d(n)} 表示。

若 N{displaystyle N} 唯一分解为 N=p1a1×p2a2×p3a3×⋯×pnan=∏i=1npiki{displaystyle N=p_{1}^{a_{1}}times p_{2}^{a_{2}}times p_{3}^{a_{3}}times cdots times p_{n}^{a_{n}}=prod _{i=1}^{n}p_{i}^{k_{i}}}, 则 d(N)=(a1+1)×(a2+1)×(a3+1)×⋯×(an+1)=∏i=1n(ai+1){displaystyle d(N)=(a_{1}+1)times (a_{2}+1)times (a_{3}+1)times cdots times (a_{n}+1)=prod _{i=1}^{n}left(a_{i}+1right)}.

例如 2646=2×33×72{displaystyle 2646=2times 3^{3}times 7^{2}}，则其正因数个数 d(2646)=(1+1)×(3+1)×(2+1)=24{displaystyle d(2646)=(1+1)times (3+1)times (2+1)=24}。

因数和

自然数.mw-parser-output .serif{font-family:Times,serif}N的正因数和，以因数函数 σ(N){displaystyle sigma (N)} 表示。由质因数分解而得。

若 N{displaystyle N} 唯一分解为 N=p1a1×p2a2×p3a3×⋯×pnan=∏i=1npiki{displaystyle N=p_{1}^{a_{1}}times p_{2}^{a_{2}}times p_{3}^{a_{3}}times cdots times p_{n}^{a_{n}}=prod _{i=1}^{n}p_{i}^{k_{i}}}, 则 σ(N)=∏i=1n(∑j=0aipij){displaystyle sigma (N)=prod _{i=1}^{n}left(sum _{j=0}^{a_{i}}p_{i}^{j}right)}.

再由等比级数求和公式可知，上式亦可写成：

σ(N)=p1a1+1−1p1−1×p2a2+1−1p2−1×⋯×pnan+1−1pn−1{displaystyle {begin{aligned}sigma (N)&={frac {p_{1}^{a_{1}+1}-1}{p_{1}-1}}times {frac {p_{2}^{a_{2}+1}-1}{p_{2}-1}}times cdots times {frac {p_{n}^{a_{n}+1}-1}{p_{n}-1}}&end{aligned}}}

例如2646=2×33×72{displaystyle 2646=2times 3^{3}times 7^{2}}，则其正因数之和

σ(2646)=(1+2)×(1+3+9+27)×(1+7+49)=22−12−1×34−13−1×73−17−1=3×40×57=6840{displaystyle {begin{aligned}sigma (2646)&=(1+2)times (1+3+9+27)times (1+7+49)\&={frac {2^{2}-1}{2-1}}times {frac {3^{4}-1}{3-1}}times {frac {7^{3}-1}{7-1}}\&=3times 40times 57\&=6840end{aligned}}}。

其他

• 所有n的正因數都是n的質因數的積的一些冪。這是算術基本定理的結果。

• 1是所有整數的正因數，-1是所有整數的負因數，因為x=1x=−1×(−x){displaystyle x=1x=-1times (-x)}
  

由上式同樣可證明，一個整數及其相反數必然為自身的因數，叫做明顯因數。

• 
  n的正因數數目是積性函數d(n)，正因數之和則是另一個積性函數σ(n)。詳見除數函數
  

• 質數p{displaystyle p}只有2個正因數：1, p{displaystyle p}。p{displaystyle p} 的平方數只有三個正因數：1, p{displaystyle p}, p2{displaystyle p^{2}}。

程式參考

给定整数的所有因数

这个程序可以打印给定正整数 n{displaystyle n} 的所有正因数。时间复杂度为 O(N){displaystyle O(N)}

C語言

#include <stdio.h>

#include <stdlib.h>

int main(void)

{

 int n=0,i; 

 printf("請輸入一個正整數Ｎ:");

 scanf("%d",&n); 

 for(i=1;i<=n;i++)

  {  

    if(n%i==0)printf("%d n",i);

  } 

 system("pause");

 return 0; 

}

AB{displaystyle A^{B}} 的因数和

这个程序可以打印 AB{displaystyle A^{B}} 的所有因数之和，由于这个答案可能很大，所以会对一个整数取模，默认为 2147483648.

C++

#include<bits/stdc++.h>



constexpr auto mod = 2147483648LL;

long int a, b;

long long n[10001], p[10001];



template<typename T>

T Prid(T a, T b) {

	T sum = 1;

	for (; b > 0; b >>= 1) {

		if (b & 1)sum = sum * a%mod;

		a = a * a%mod;

	}

	return sum;

}



template<typename T>

T Get_Sum(T p, T n) {

	if (n == 0)return 1;

	if (n & 1)return (Get_Sum(p, (n >> 1))*(1 + Prid(p, (n >> 1) + 1))) % mod;

	else return (Get_Sum(p, (n >> 1) - 1)*(1 + Prid(p, (n >> 1) + 1)) + Prid(p, (n >> 1))) % mod;

}



int main()

{

	std::cin >> a >> b;

	unsigned int nowAt = 0;



	for (int i = 2; i*i <= a; i += (i == 2 ? 1 : 2))

		if (a%i == 0) {

			p[nowAt] = i;

			n[nowAt] = 0;

			while (a%i == 0) { ++n[nowAt]; a /= i; }

			++nowAt;

		}

	if (a != 1) {

		p[nowAt] = a; n[nowAt++] = 1;

	}



	long long ans = 1;

	for (int i = 0; i < nowAt; i++)

		ans = (ans*Get_Sum(p[i], n[i] * b)) % mod;



	std::cout << ans << std::endl;



	system("pause");

	return 0;

}

C#

using System;

namespace DS

{

	class Program

	{

		public static class Global

		{

			public static readonly Int64 mod = 2147483648;

		}

			

		static void Main(string args)

		{

			string div = Console.ReadLine().Split(' ');

			Int64 a = Convert.ToInt64(div[0]), b = Convert.ToInt64(div[1]);

			uint nowAt = 0;



			Int64 p = new Int64[10001], n = new Int64[10001];



			for (int i = 2; i * i <= a; i += (i == 2 ? 1 : 2))

				if (a % i == 0)

				{

					p[nowAt] = i;

					n[nowAt] = 0;

					while (a % i == 0) { ++n[nowAt]; a /= i; }

					++nowAt;

				}

			if (a != 1)

			{

				p[nowAt] = a; n[nowAt++] = 1;

			}



			Int64 ans = 1;

			for (int i = 0; i < nowAt; i++)

				ans = (ans * Get_Sum(p[i], n[i] * b)) % Global.mod;



			Console.WriteLine(ans.ToString());

		}



		static Int64 Prid(Int64 a,Int64 b)

		{

			Int64 sum = 1;

			for (; b > 0; b >>= 1)

			{

				if ((b & 1) == 1) sum = sum * a % Global.mod;

				a = a * a % Global.mod;

			}return sum;

		}



		static Int64 Get_Sum(Int64 p,Int64 n)

		{

			if (n == 0) return 1;

			if ((n & 1) == 1) return (Get_Sum(p, (n >> 1)) * (1 + Prid(p, (n >> 1) + 1))) % Global.mod;

			else return (Get_Sum(p, (n >> 1) - 1) * (1 + Prid(p, (n >> 1) + 1)) + Prid(p, (n >> 1))) % Global.mod;

		}

	}

}

相關條目

• 因數判別法可參照整除規則。


• 質數


• 同余


• 質因數


• 
  公倍數、最小公倍數
  


• 
  公因數、最大公因數
  

查 论 编 和因數有關的整數分類 簡介 質因數分解 因數 元因數 除數函數 質因數 算术基本定理 依因數分解分類 素数 合数 半素数 普洛尼克数 楔形数 无平方数因数的数 冪數 次方數 阿喀琉斯數 光滑數 正规数 粗糙數 不尋常數 依因數和分類 完全数 殆完全數 准完全数 多重完全數‎‎ Hemiperfect數 en:Hyperperfect number 超完全數 元完全數 半完全数 實際數 有許多因數 过剩数 本原過剩數 高過剩數‎ 超過剩數 Colossally過剩數 高合成数 en:Superior highly composite number 奇異數 和真因子和數列有關 不可及数 相亲数 交際數 婚約數 其他 亏数 友誼數 孤獨數 卓越数 歐爾調和數 佩服數 節儉數 等數位數 奢侈數

查 论 编 分數 & 比率 除法 ＆比例 被除數 : 除數 = 商數 分數 分子/分母=商數 代數 Aspect 连分数 十进制 二进分数 古埃及分數 黄金分割率 白銀比例 整数 最简分数 精簡 最小公分母 音程 百分比 單位分數