數(shù)論基礎(chǔ)算法word版-資料下載頁
2025-08-21 22:58本頁面
【正文】 gint):boolean。var i:integer。beginfor i:=1 to pnum doif sqr(p[i])=x then begin if x mod p[i]=0 then begin IsPrime:=false。 exit。 end。endelse begin IsPrime:=true。 exit。end。IsPrime:=true。end。procedure main。var x:longint。beginpnum:=0。x:=1。while(pnumn) dobegininc(x)。if IsPrime(x) then begin inc(pnum)。 p[pnum]:=x。 end。end。end。procedure out。var i,t:integer。beginfor i:=1 to n dobeginwrite(p[i]:5)。t:=t+1。if t mod 10=0 then writeln。end。end。beginreadln(n)。main。out。end.:求不大于n的所有素?cái)?shù)program sushu3。const maxn=10000。vari,k,n:integer。a:array[1..maxn] of integer。beginreadln(n)。for i:=1 to n do a[i]:=i。a[1]:=0。i:=2。while in dobegink:=2*i。while k=n do begin a[k]:=0。 k:=k+i。 end。i:=i+1。while (a[i]=0) and (in) do i:=i+1。end。k:=0。for i:=1 to n doif a[i]0 then begin write(a[i]:5)。 k:=k+1。 if k mod 10 =0 then writeln。 endend.:將整數(shù)分解質(zhì)因數(shù)的積program BasicMath_PolynomialFactors。constmaxp=1000。varpnum,n:longint。num,p:array[1..maxp] of longint。procedure main。var x:longint。beginfillchar(num,sizeof(num),0)。fillchar(p,sizeof(p),0)。pnum:=0。x:=1。while(n1) do begin inc(x)。 if n mod x=0 then begin inc(pnum)。 p[pnum]:=x。 while(n mod x=0) do begin n:=n div x。 inc(num[pnum])。 end。 end。end。end。procedure out。var j,i:integer。beginfor i:=1 to pnum dofor j:=1 to num[i] dowrite(p[i]:5)。writeln。end。beginmain。out。end.+by=c的整數(shù)解及應(yīng)用 ：求方程ax+by=c的整數(shù)解 procedure equation(a,b,c:longint。var x0,y0:longint)。var d,x,y:longint。begind:=exgcd(a,b,x,y)。if c mod d0 thenbegin writeln(39。no answer39。)。 halt。end elsebegin x0:=x*(c div d)。 y0:=y*(c div d)。end。end。 +by=c整數(shù)解的應(yīng)用 例1：有三個(gè)分別裝有a升水、b升水和c升水的量筒(gcd(a，b)＝1，cba0),現(xiàn)c筒裝滿水，問能否在c筒個(gè)量出d升水(cd0)。若能，請(qǐng)列出一種方案。算法分析：量水過程實(shí)際上就是倒來倒去，每次倒的時(shí)候總有如下幾個(gè)持點(diǎn)：；2．不是一個(gè)筒被倒?jié)M就是另一個(gè)筒被倒光；3．c筒僅起中轉(zhuǎn)作用，而本身容積除了必須足夠裝下a簡和b簡的全部水外，別無其 它限制。 程序如下: program mw。typenode=array[0..1] of longint。vara,b,c:node。d,step,x,y:longint。function exgcd(a,b:longint。var x,y:longint):longint。var t:longint。beginif b=0 then begin exgcd:=a。x:=1。y:=0。 end else begin exgcd:=exgcd(b,a mod b,x,y)。 t:=x。x:=y。y:=t(a div b)*y end。end。procedure equation(a,b,c:longint。var x0,y0:longint)。var d,x,y:longint。begind:=exgcd(a,b,x,y)。if c mod d0 thenbegin writeln(39。no answer39。)。 halt。end elsebegin x0:=x*(c div d)。 y0:=y*(c div d)。end。end。procedure fill(var a,b:node)。var t:longint。beginif a[1]b[0]b[1] then t:=a[1] else t:=b[0]b[1]。a[1]:=a[1]t。b[1]:=b[1]+tend。beginwrite(39。a,b,c,d=39。)。readln(a[0],b[0],c[0],d)。equation(a[0],b[0],d,x,y)。step:=0。a[1]:=0。b[1]:=0。c[1]:=c[0]。writeln(step:5,39。:39。,a[1]:5,b[1]:5,c[1]:5)。if x0 then repeat if a[1]=0 then fill(c,a) else if b[1]=b[0] then fill(b,c) else fill(a,b)。 inc(step)。 writeln(step:5,39。:39。,a[1]:5,b[1]:5,c[1]:5)。 until c[1]=d else repeat if b[1]=0 then fill(c,b) else if a[1]=a[0] then fill(a,c) else fill(b,a)。 inc(step)。 writeln(step:5,39。:39。,a[1]:5,b[1]:5,c[1]:5)。 until c[1]=d。end. 求a^b mod n :直接疊代法求a^b mod n function f(a,b,n:longint): longint。 var d,i:longint。 begin d:=a。 for i:=2 to b do d:=d mod n*a。 d:=d mod n。 f:=d。 end。 :加速疊代法 function f(a,b,n:longint):longint。 var d,t:longint。 begin d:=1。t:=a。 while b0 do begin if t=1 then begin f:=d。exit end 。 if b mod 2 =1 then d:=d*t mod n。 b:=b div 2。 t:=t*t mod n。 end。 f:=d end。 練習(xí)： .
法律信息相關(guān)推薦
鄂ICP備17016276號(hào)-1