本页使用了标题或全文手工转换

因數

维基百科,自由的百科全书
跳到导航 跳到搜索

因数(又称约数)是一个常见的数学名词,用于描述非零整数 整数 之间存在的整除关系,即 可以被 整除。这里我们称 倍数因数约数因子.

定义[编辑]

满足 . 若存在 使得 , 那么就说 倍数约数。这种关系记作 ,读作“ 整除 ”.

例如 . 所以 ,同时 的因数; 的因数。


性质[编辑]

  • 那么 .
  • , 有 .
  • , 设 , 那么 .
  • , 那么 充要条件
  • 满足 那么 .

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

证毕。


相关定理[编辑]

整数的唯一分解定理[编辑]

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

如果 , 那么

, 其中 是一个素数.

这种表示方法是唯一的。

因数个数[编辑]

自然数 的因数个数以 表示。

唯一分解为 , 则 .

例如 ,则其正因数个数

因数和[编辑]

自然数N的正因数和,以因数函数 表示。由质因数分解而得。

唯一分解为 , 则 .

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

例如,则其正因数之和

其他[编辑]

  • 1是所有整數的正因數,-1是所有整數的負因數,因為

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

  • 質數只有2個正因數:1, 平方數只有三個正因數:1, ,

程式參考[编辑]

给定整数的所有因数[编辑]

这个程序可以打印给定正整数 的所有正因数。时间复杂度为

C語言[编辑]

#include <stdio.h>
#include <stdlib.h>
int main(void)
{
 int n=0,i; 
 printf("請輸入一個正整數N:");
 scanf("%d",&n); 
 for(i=1;i<=n;i++)
  {  
    if(n%i==0)printf("%d \n",i);
  } 
 system("pause");
 return 0; 
}

的因数和[编辑]

这个程序可以打印 的所有因数之和,由于这个答案可能很大,所以会对一个整数取模,默认为 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;
		}
	}
}

相關條目[编辑]