编程分解质因数 分解质因数 分解质因数-基本内容,分解质因数-编程分解

任何一个合数都可以写成几个质数相乘的形式。其中每个质数都是这个合数的因数,叫做这个合数的分解质因数。分解质因数只针对合数。

什么是分解质因数_分解质因数 -基本内容

原理

任何一个

合数都可以写成几个

质数相乘的形式。其中每个质数都是这个合数的

因数,叫做这个合数的分解

质因数。

分解质因数只针对合数。

方法

举个简单例子,12的分解质因数可以有以下几种:12=2x2x3=4x3=1x12=2x6,其中1,2,3,4,6,12都可以说是12的因数,即相乘的几个数等于一个

自然数,那么这几个数就是这个自然数的因数。2,3,4中,2和3是质数,就是质因数,4不是质数。那么什么是质数呢?就是不能再拆分为除了1和它本身之外的因数的数,如2,3,5,7,11,13,17,19,23,29等等,质数没有什么特定的规律,不存在最大的质数。

求一个数分解质因数,要从最小的质数除起,一直除到结果为质数为止。分解质因数的算式的叫

短除法,和除法的性质差不多,还可以用来求多个个数的公因式:

如24

2┖24(是短除法的符号)

2┖12

2┖6

3――3是质数,结束

得出24=2×2×2×3=2^3×3(m^n=m的n次方)

再如105

3┖105

5┖35

7――7是质数,结束

得出105=3×5×7

证明,不存在最大的质数:

使用反证法:

假设存在最大的质数为N,则所有的质数序列为:N1,N2,N3……N

设M=(N1×N2×N3×N4×……N)+1,

可以证明M不能被任何质数整除,得出M是也是一个质数。

而M>N,与假设矛盾,故可证明不存在最大的质数。

Pollard Rho快速因数分解

1975年,John M. Pollard提出了第二种因数分解的方法。该算法时间复杂度为O(n^(1/4))。详见参考资料。

什么是分解质因数_分解质因数 -编程分解

pascal语言

program dsq;

var

n,i:longint;

begin

readln(n);

write(n,'=1');

i:=2;

while i

while n mod i = 0 do begin

write('*',i);

n:=n div i;

end;

inc(i);

end;

end.

Java


分解质因数

VisualBasic语言

Dim x,a,b,k As String

Private Sub Command1_Click()

a = Val(Text1.Text)

x = 2

If aInt(a) Then

If a = 1 Then

Text2.Text = "它既不是质数,也不是合数"

Else

MsgBox "请您先输入数据",vbOKOnly + vbInformation,"友情提示"

End If

Else

Do While a / 2 = Int(a / 2) And a>= 4

If b = 0 Then

Text2.Text = Text2.Text & "2"

b = 1

Else

Text2.Text = Text2.Text & "*2"

编程分解质因数 分解质因数 分解质因数-基本内容,分解质因数-编程分解

End If

a = a / 2

k = a

Loop

Do While a>1

For x = 3 To Sqr(a) Step 2

Do While a / x = Int(a / x) And a>= x * x

If b = 0 Then

Text2.Text = Text2.Text & x

b = 1

Else

Text2.Text = Text2.Text & "*" & x

End If

a = a / x

Loop

Next

k = a

a = 1

Loop

If b = 1 Then

Text2.Text = Text2.Text & "*" & k

Else

Text2.Text = "这是一个质数"

End If

End If

End Sub

Private Sub Command2_Click()

Text1.Text = ""

Text2.Text = ""

End Sub

c语言

#include

#include

int main() {

int i,b;

long long in; /*采用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;

}

C++语言

#include

#include

#include

using namespace std;

int main()

{

int n,i;

cout

cin>>n;

if(n

{

cout

exit(-1);

}

cout

while(n % 2 == 0 && n != 2)

{

cout

n /= 2;

}

int val = sqrt(n);

for(i = 3; i

{

while(val>= i)

{

if(n % i == 0)

{

cout

n /= i;

val = sqrt(n);

}

else

break;

}

}

cout

return 0;

}

CommonLisp

(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)))))))

批处理分解质因数脚本

@echo off

color 1e

:start

cls

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=

:loop_1

if %num% EQU 1 goto result

set count=3

set /a mod=num%%2

if %mod% EQU 0 (

set numx=%numx%×2

set /a num=num/2

goto loop_1

:loop_2

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

cls

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

:result

cls

set numx=%numx:~2%

if %num0% EQU %numx% echo %num0%是素数,不能分解!&pause>nul&goto start

echo %num0%=%numx%

pause>nul

goto start

  

爱华网本文地址 » http://www.413yy.cn/a/8104100103/176710.html

更多阅读

dnf分解机怎么修 dnf史诗爆率最高的图

dnf分解机怎么修——简介DNF分解机是《地下城与勇士》中副职业分解师的一种分解设备,分解师可以将分解机放在城镇的任何地方供其他玩家分解武器装备,分解的过程中分解机的耐久度会降低,如果耐久度将为0,分级机就不能使用,就必须维修。dn

dnf分解机的零件怎么获得 精 dnf分解机的零件

dnf分解机的零件怎么获得 精——简介 《地下城与勇士》是一款韩国网络游戏公司NEOPLE开发的免费色扮演2D游戏,由三星电子发行,并于2005年8 月在韩国正式发布。该游戏是一款2D卷轴式横版格斗过关网络游戏 (MMOACT),大量继承了众多家用机

dnf分解机耐久度为0怎么办 dnf怎么升级分解机

dnf分解机耐久度为0怎么办——简介大家都知道装备分解机是有耐久度的,随着我们的不断使用,分解机耐久度为0,无法分解装备了怎么办?DNF分解机坏了怎么修?dnf分解机耐久度为0怎么办——工具/原料装备分解机dnf分解机耐久度为0怎么办——新

分解机怎么升级 精 dnf的分解机怎么升级

分解机怎么升级 精——简介《地下城与勇士》是一款韩国网络游戏公司NEOPLE开发的免费角色扮演2D游戏,由三星电子发行,并于 2005年8月在韩国正式发布。该游戏是一款2D卷轴式横版格斗过关网络游戏 (MMOACT),大量继承了众多家用机、街机2D

太极一章至八章的分解动作 太极四章分解动作视频

太极一章至八章的分解动作——简介所谓“章”,就相当于我国武术界所说的套路,即将一定数量的动作编排串连,形成一套具有一定特点和难度的统一模式套路。这样演练起来,即能融汇贯通,腿、脚、身、臂俱练,又能互相结合,互相配合。跆拳道中的

声明:《编程分解质因数 分解质因数 分解质因数-基本内容,分解质因数-编程分解》为网友幸福是被你需要分享!如侵犯到您的合法权益请联系我们删除