分解质因数_百度百科
清除历史记录关闭
声明：百科词条人人可编辑，词条创建和修改均免费，绝不存在官方及代理商付费代编，请勿上当受骗。
分解质因数
每个合数都可以写成几个相乘的形式，其中每个质数都是这个的因数，叫做这个合数的。 分解质因数只针对合数。
分解质因数定义
把一个合数分解成若干个质因数的乘积的形式，即求质因数的过程叫做分解质因数。
分解质因数只针对合数。（分解质因数也称分解素因数）求一个数分解质因数，要从最小的质数除起，一直除到结果为质数为止。分解质因数的算式叫，和除法的性质差不多，还可以用来求多个个数的。
分解质因数定理
不存在最大质数的证明：（使用反证法）
假设存在最大的质数为N，则所有的质数序列为：N1，N2，N3……N
设M=（N1×N2×N3×N4×……N）+1，
可以证明M不能被任何质数，得出M也是一个质数。
而M&N，与假设，故可证明不存在最大的。
第二种因数分解的方法：
1975年，John M. Pollard提出。该算法时间复杂度为O(
)。详见参考资料
分解质因数编程分解
&&&&&&&&static&void&Main(string[]&args)
&&&&&&&&&&&&&&&&Practice3();
&&&&&&&&private&static&void&Practice3()
&&&&&&&&&&&&List&int&&a&=&new&List&int&();&&&&&&&&//用于存放质因数
&&&&&&&&&&&&Console.WriteLine(&请输入一个整数：&);
&&&&&&&&&&&&int&n&=&Convert.ToInt32(Console.ReadLine());
&&&&&&&&&&&&int&o&=&n;&&&&&&&&&&&&&&&&&&&&&&&&&&&&//用于存放输入的整数
&&&&&&&&&&&&for&(int&x&=&2;&x&&=&n;&x++)
&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&if(n%x&==&0)
&&&&&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&&&&&n/=x;
&&&&&&&&&&&&&&&&&&&&a.Add(x);
&&&&&&&&&&&&&&&&&&&&x--;&&&&&&&&&&&&&&&&&&&&&&&&&&&//为了防止该整数有多个相同质因数最终只能输出一个的情况
&&&&&&&&&&&&&&&&}
&&&&&&&&&&&&}
&&&&&&&&&&&&Console.WriteLine(&{0}={1}&,o,string.Join(&*&,a.ToArray()));
另一种实现
#include&&stdio.h&
Integer&m,b,c&:=&0,j&:=&0;
Integer&a[10];&//存放质因数
Integer&fjzys(Integer&k)
Integer&i&:=&2;
while&(k&&:=&i)&do&//判断k是否合格
if&(k&mod&i=0)&then&//判断k是否整除当前因数
a[j]&:=&i;&//存入因数
k/&:=&i;&//余数
i&:=&2;&//令i重新等于2
j++;&//计数值
i++;&//不能整除则当前因数为非质因数
(*&C2PAS:&Exit&*)&Result&:=&0;
(*&用for实现上面的函数
int&fjzys(int&k)
for&(&;&i&=k&;&i++&)&//当因数i&=k时，实现该循环，每次循环因数i自加1
for&(&;&k%i==0&;&j++&)&//当k整除当前因数，实现该循环，每次循环下标j自加1
k/=i;&//使k=k/i
a[j]=i;&//存入因数
解决上面的函数，无法输出，多个相同的质因数，如90=2*3*3*5，只能输出一个3.
void&main()
printf('请输入一个整数'#10'k=');
scanf('%d',&(*&C2PAS:&RefOrBit?&*)&m);
for(b&:=&0;b&(j-1);b++)&//*比质因数少一个
printf('%d',a[b]);
printf('*');
printf('%d'#10'',a[j-1]);&//输出最后一个质因数
//Pascal实现方法于更改，此前版本亲测错误
//Pascal实现方法于再次更改，将可处理数字的范围扩大了
注意，此程序在处理过大的数字时速度不佳，在各大OJ上估计都会TLE几个测试数据
&&n&:&Int64&;
&&i&:&Longint&;
&&readln(&n&)&;
&&if&n&&1&
&&&&then&write(&n&,&'='&)
&&&&else&write(&n&,&'=1'&);
&&i&:=&2&;
&&while&n&&1&do&
&&&&&&if&(&n&mod&i&)=0&
&&&&&&&&then&Begin
&&&&&&&&&&&&&&&n&:=&n&div&i&;
&&&&&&&&&&&&&&&write(&i&);
&&&&&&&&&&&&&&&if&n&&1
&&&&&&&&&&&&&&&&&then&write(&'*'&);
&&&&&&&&&&&&&&&i&:=&2&;
&&&&&&&&&&&&&End
&&&&&&&&else&inc(&i&)&;
//By&Cubeneo（和之前的Rh。是同一个人）
import&java.util.S
public&class&H6&{
&&&&public&static&void&main(String[]&args)&{
&&&&&&&&System.out.println(&输入所求正整数:&);
&&&&&&&&Scanner&sc&=&new&Scanner(System.in);
&&&&&&&&Long&n&=&sc.nextLong();
&&&&&&&&long&m=n;
&&&&&&&&int&flag&=&0;
&&&&&&&&String[]&str&=&new&String[50];
&&&&&&&&for&(long&i&=&2;&i&&=&n;&i++)&{
&&&&&&&&&&&&if&(n&%&i&==&0)&{
&&&&&&&&&&&&&&&&str[flag]&=&Long.toString(i);
&&&&&&&&&&&&&&&&flag++;
&&&&&&&&&&&&&&&&n&=&n&/&i;
&&&&&&&&&&&&&&&&i--;
&&&&&&&&&&&&}
&&&&&&&&if&(flag&&&2)
&&&&&&&&&&&&System.out.println(m&+&&为质数&);
&&&&&&&&else&{
&&&&&&&&&&&&System.out.print(m&+&&=&&+&str[0]);
&&&&&&&&&&&&for&(int&k&=&1;&k&&&&k++)&{
&&&&&&&&&&&&&&&&System.out.print(&*&&+&str[k]);
&&&&&&&&&&&&}
&&&&&&&&&&&&System.out.println(&\n&+m+&共有&+flag+&个质因数.&);
&&&&&&&&sc.close();
此方法最多可分解包含50个质数的合数.&&@author寒鸦LMC
Visual Basic
Dimx,a,b,kAsString
PrivateSubCommand1_Click()
a=Val(Text1.Text)
Ifa&=1Ora&Int(a)Then
Text2.Text=&它既不是质数，也不是合数&
MsgBox&请您先输入数据&,vbOKOnly+vbInformation,&友情提示&
DoWhilea/2=Int(a/2）Anda&=4
Text2.Text=Text2.Text&&2&
Text2.Text=Text2.Text&&*2&
DoWhilea&1
Forx=3ToSqr(a)Step2
DoWhilea/x=Int(a/x)Anda&=x*x
Text2.Text=Text2.Text&x
Text2.Text=Text2.Text&&*&&x
Text2.Text=Text2.Text&&*&&kv
Text2.Text=&这是一个质数&
PrivateSubCommand2_Click()
Text1.Text=&&
Text2.Text=&&
EndSubc语言
实现一，此代码因为用了long long int，为C99标准，故不可在VC6.0上运行。　　
#include&&stdio.h&
#include&&math.h&
int&main()
&&&&int&i,b;
&&&&long&long&int&
/*采用64位整型，以便输入更大的数*/
&&&&freopen(&F://1.txt&,&r&,stdin);
&&&&freopen(&F://2.txt&,&w&,stdout);
&&&&while(scanf(&%lld&,&in)!=EOF)
&&&&&&&&/*在F://1.txt中输入x个数N（N&=2）以换行符或空格符隔开，当没有输入时循环会自动结束*/
&&&&&&&&b=0;/*用于标记是否是第一个质因数，第一个质因数在输出时前面不需要加空格*/
&&&&&&&&for(i=2;in!=1;i++)
&&&&&&&&&&&&if(in%i==0)
&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&in/=i;
&&&&&&&&&&&&&&&&b?printf(&%d&,i):printf(&%d&,i),b=1;
&&&&&&&&&&&&&&&&i--;
&&&&&&&&/*i--和i++使得i的值不变，即能把N含有的所有的当前质因数除尽，例如：24会一直把2除尽再去除3*/
&&&&&&&&&&&&}
&&&&&&&&printf(&\n&);
&&&&return&0;
可直接在VC6.0运行。
#include&&stdio.h&
int&m,b,c=0,j=0;
int&a[10];&&&&//存放质因数
int&fjzys(int&k)
&&&&int&i=2;
&&&&while(k&=i)&&&&//判断k是否合格&&&&&&&
&&&&&&&&if(k%i==0)&&&&//判断k是否整除当前因数
&&&&&&&&&&&&a[j]=i;&&&&//存入因数
&&&&&&&&&&&&k/=i;&&&&//余数
&&&&&&&&&&&&i=2;&&&&//令i重新等于2
&&&&&&&&&&&&j++;&&&&//计数值
&&&&&&&&else
&&&&&&&&&&&&i++;&&&&//不能整除则当前因数为非质因数
&&&&return&0;
/*&用for实现上面的函数
int&fjzys(int&k)
&&&&int&i=2;
&&&&for&(&;&i&=k&;&i++&)&&&&//当因数i&=k时，实现该循环，每次循环因数i自加1
&&&&&&&&for&(&;&k%i==0&;&j++&)&&&//当k整除当前因数，实现该循环，每次循环下标j自加1
&&&&&&&&&&&&k/=i;&&&//使k=k/i
&&&&&&&&&&&&a[j]=i;&&&//存入因数
&&&&return&0;
解决上面的函数，无法输出，多个相同的质因数，如90=2*3*3*5，只能输出一个3.
int&main()
&&&&printf(&请输入一个整数\nk=&);
&&&&scanf(&%d&,&&m);
&&&&fjzys(m);
&&&&for(b=0;b&(j-1);b++)&&&&//*比质因数少一个
&&&&&&&&printf(&%d&,a[b]);
&&&&&&&&printf(&*&);
&&&&printf(&%d\n&,a[j-1]);&&&&//输出最后一个质因数
&&&&return&0;
//将一个数n分解为若干个从小到大排列的质数的积
#include&&iostream&
using&namespace&
int&main()
&&&&int&n,&n2;
&&&&cin&&&&n;&&
&&&&cout&&&&n&&&&&=&;
&&&&n2&=&n;
&&&&if（n&2）return&0;&&&&&&&&&&&&&&&&//小于2的数不合法，若n为质数则输出它本身
&&&&for(int&i&=&2;i*i&=n2;i++)&&&&&&&&//根号n复杂度
&&&&{&&&&&&&&
&&&&&&&&while(n2%i==0)
&&&&&&&&&&&&n2=n2/i;
&&&&&&&&&&&&cout&&&&i&;
&&&&&&&&&&&&if(n2!=1)cout&&&&&*&;
&&&&if（n2！=1）&&&&cout&&&&n2;&&&&&&&&//当n为质数
&&&&return&0;
Common Lisp
(defun is-prime-number (number)　　(let ((num number))　　(do ((index 2 （1+ index)))　　((&= index num) t)　　(if (= 0 (mod num index))　　(return-from is-prime-number nil)))))　　(defun decomposition-quality-factor (number)　　(let ((num number) (prime-list (make-array 10 :fill-pointer 0 :adjustable t)))　　(if (is-prime-number num)　　(progn　　(format t &~a~%& num)　　(return-from decomposition-quality-factor nil)))　　(do ((index 2 （1+ index)))　　((&= index num) nil)　　(if (is-prime-number index)　　(push index prime-list)))　　(dolist (value prime-list)　　(let ((test-flag nil))　　(do ()　　(test-flag nil)　　(if (= 0 (mod num value))　　(progn　　(format t &~a~%& value)　　(setf num (/ num value))　　(if (is-prime-number num)　　(progn　　(format t &~a~%& num)　　(return-from decomposition-quality-factor nil))))　　(setf test-flag t)))))))
Python2.x分解质因数
#!/usr/bin/python
#&-*-&coding:utf-8&-*-
num&=&int(raw_input(&请输入要分解的正整数：&))
while&num!=1:
&&&&for&i&in&range(2,num+1):
&&&&&&&&if&num%i&==&0:
&&&&&&&&&&&&temp.append(i)
&&&&&&&&&&&&num&/=&i
&&&&&&&&&&&&break
print&temp
Python3.x分解质因数
#MillerRabin素数判定,结合Pollard_rho递归分解,效率极高
import&random
from&collections&import&Counter
def&gcd(a,&b):
&&&&if&a&==&0:
&&&&&&&&return&b
&&&&if&a&&&0:
&&&&&&&&return&gcd(-a,&b)
&&&&while&b&&&0:
&&&&&&&&c&=&a&%&b
&&&&&&&&a,&b&=&b,&c
&&&&return&a
def&mod_mul(a,&b,&n):
&&&&result&=&0
&&&&while&b&&&0:
&&&&&&&&if&(b&&&1)&&&0:
&&&&&&&&&&&&result&=&(result&+&a)&%&n
&&&&&&&&a&=&(a&+&a)&%&n
&&&&&&&&b&=&(b&&&&1)
&&&&return&result
def&mod_exp(a,&b,&n):
&&&&result&=&1
&&&&while&b&&&0:
&&&&&&&&if&(b&&&1)&&&0:
&&&&&&&&&&&&result&=&mod_mul(result,&a,&n)
&&&&&&&&a&=&mod_mul(a,&a,&n)
&&&&&&&&b&=&(b&&&&1)
&&&&return&result
def&MillerRabinPrimeCheck(n):
&&&&if&n&in&{2,&3,&5,&7,&11}:
&&&&&&&&return&True
&&&&elif&(n&==&1&or&n&%&2&==&0&or&n&%&3&==&0&or&n&%&5&==&0&or&n&%&7&==&0&or&n&%&11&==&0):
&&&&&&&&return&False
&&&&k,&u&=&0,&n&-&1
&&&&while&not&(u&&&1)&&&0:
&&&&&&&&k&+=&1
&&&&&&&&u&=&(u&&&&1)
&&&&random.seed(0)
&&&&for&i&in&range(s):
&&&&&&&&x&=&random.randint(2,&n&-&1)
&&&&&&&&if&x&%&n&==&0:
&&&&&&&&&&&&continue
&&&&&&&&x&=&mod_exp(x,&u,&n)
&&&&&&&&pre&=&x
&&&&&&&&for&j&in&range(k):
&&&&&&&&&&&&x&=&mod_mul(x,&x,&n)
&&&&&&&&&&&&if&(x&==&1&and&pre&!=&1&and&pre&!=&n&-&1):
&&&&&&&&&&&&&&&&return&False
&&&&&&&&&&&&pre&=&x
&&&&&&&&if&x&!=&1:
&&&&&&&&&&&&return&False
&&&&&&&&return&True
def&Pollard_rho(x,&c):
&&&&(i,&k)&=&(1,&2)
&&&&x0&=&random.randint(0,&x)
&&&&y&=&x0
&&&&while&1:
&&&&&&&&i&+=&1
&&&&&&&&x0&=&(mod_mul(x0,&x0,&x)&+&c)&%&x
&&&&&&&&d&=&gcd(y&-&x0,&x)
&&&&&&&&if&d&!=&1&and&d&!=&x:
&&&&&&&&&&&&return&d
&&&&&&&&if&y&==&x0:
&&&&&&&&&&&&return&x
&&&&&&&&if&i&==&k:
&&&&&&&&&&&&y&=&x0
&&&&&&&&&&&&k&+=&k
def&PrimeFactorsListGenerator(n):
&&&&result&=&[]
&&&&if&n&&=&1:
&&&&&&&&return&None
&&&&if&MillerRabinPrimeCheck(n):
&&&&&&&&return&[n]
&&&&while&p&&=&n:
&&&&&&&&p&=&Pollard_rho(p,&random.randint(1,&n&-&1))
&&&&result.extend(PrimeFactorsListGenerator(p))
&&&&result.extend(PrimeFactorsListGenerator(n&//&p))
&&&&return&result
def&PrimeFactorsListCleaner(n):
&&&&return&Counter(PrimeFactorsListGenerator(n))
&&&&&&&&&&&&&&&&&&
PrimeFactorsListCleaner()
Bash Shell分解质因数脚本
#!/usr/bin/bash
read input
factor &$input&
批处理分解质因数脚本
&&&&title&分解质因数程序
&&&&set&/p&num=请输入待分解的数
&&&&set&num0=%num%
&&&&if&%num%&EQU&1&cls&echo&1既不是素数也不是非素数，不能分解&pause&&nul&goto&start
&&&&if&%num%&EQU&2&cls&echo&2是素数，不能分解&pause&&nul&goto&start
&&&&if&%num%&EQU&3&cls&echo&3是素数，不能分解&pause&&nul&goto&start
&&&&set&numx=
&&&&if&%num%&EQU&1&goto&result
&&&&set&count=3
&&&&set&/a&mod=%num%%%2
&&&&echo&%mod%
&&&&if&%mod%&EQU&0&(&set&numx=%numx%×2&&&set&/a&num=num/2&&&&goto&loop_1&)
&&&&set&/a&mod=%num%%%%count%
&&&&if&%mod%&EQU&0&(&set&numx=%numx%×%count%&&&set&/a&num=num/count&)
&&&&if&%num%&EQU&1&goto&result
&&&&if&%count%&EQU&%num%&set&numx=%numx%×%count%&&goto&result
&&&&set&/a&stop=%count%*%count%
&&&&if&%stop%&GTR&%num%&set&numx=%numx%×%num%&&&goto&result
&&&&set&/a&count+=2
&&&&echo&正在计算......
&&&&echo&%num0%=%numx:~2%
&&&&set&/a&wc=stop*100/num
&&&&echo&正在计算%num%的因数
&&&&echo&已完成计算%wc%%%
&&&&if&%mod%&EQU&0&goto&loop_1
&&&&goto&loop_2
&&&&set&numx=%numx:~1%
&&&&if&%num0%&EQU&%numx%&echo&%num0%是素数，不能分解！&pause&&nul&goto&start
&&&&echo&%num0%=%numx%
&&&&pause&&nul
&&&&goto&start
function&prime(maxValue){
&&&&var&minPrime&=&2;
&&&&var&primes&=&[minPrime];
&&&&for(var&i=3;i&=maxVi++){
&&&&&&&&var&isPrime&=&
&&&&&&&&for(var&p=0;p&primes.p++){
&&&&&&&&&&&&if(i&%&primes[p]&==&0){
&&&&&&&&&&&&&&&&isPrime&=&
&&&&&&&&&&&&&&&&
&&&&&&&&&&&&}
&&&&&&&&if(isPrime){
&&&&&&&&&&&&primes.push(i);
&&&&return&
function&decomposition(v){
&&&&var&results&=&[];
&&&&var&primes&=&prime(v);
&&&&var&tmp&=&v;
&&&&for(var&i=0;i&primes.i++){
&&&&&&&&if(tmp&==&primes[i]){
&&&&&&&&&&&&results.push(primes[i]);
&&&&&&&&&&&&
&&&&&&&&while(tmp&%&primes[i]==0){
&&&&&&&&&&&&tmp&/=&primes[i];
&&&&&&&&&&&&results.push(primes[i]);
&&&&if(results.length&==&1){
&&&&&&&&results&=&[];
&&&&&&&&results.push(1);
&&&&&&&&results.push(v);
&&&&return&
清除历史记录关闭