主题:求教:从键盘键入一整数,fortran编程输出该整数的所有质因子
yanglei2006
[专家分:0] 发布于 2010-04-07 23:43:00
求教:从键盘键入一整数,fortran编程输出该整数的所有质因子
非常感谢
最后更新于:2010-04-07 23:44:00
回复列表 (共13个回复)
沙发
asymptotic [专家分:16630] 发布于 2010-04-07 23:45:00
这个问题有现成的算法解决吗?我以前似乎看到过大整数加密,就是分解质因数。
板凳
yanglei2006 [专家分:0] 发布于 2010-04-08 00:05:00
没有现成的算法啊,C语言很容易实现,但一碰到fortran编程就搞不定了。多谢啊
3 楼
齐东野人 [专家分:1920] 发布于 2010-04-08 01:33:00
只能穷举
判断小于此数的所有数是否是质因子
4 楼
aozhouyang [专家分:0] 发布于 2010-04-08 18:16:00
穷举的话
只要判断小于其 1/2 的整数就行了
5 楼
yrliu [专家分:750] 发布于 2010-04-08 20:47:00
How about the following codes?
------------------------------------------
program factt
implicit none
integer :: n,i,isprime
do
read*,n
n=abs(n)
if( n.le. 1) print*,n
100 do i=2,n
if(mod(n,i) .eq. 0)then
if(isprime(i)) then
print*,i
n=n/i
goto 100
endif
endif
enddo
enddo
end program
integer function isprime(k)
implicit none
integer::k,i,j
i=abs(k)
if(i .le. 1)then
isprime=0
return
elseif(i .eq. 2)then
isprime=1
return
elseif(mod(i,2) .eq. 0) then
isprime=0
return
else
do j=3, i-2,2
if(mod(i,j) .eq. 0) then
isprime=0
return
endif
enddo
isprime=1
return
endif
end function
6 楼
weixing1531 [专家分:2580] 发布于 2010-04-08 23:05:00
穷举的话
只要判断小于其[color=FF0000]平方根[/color]的整数就行了
目前还没有非常快速的算法
正因为如此
一个非常大的整数找到其所有质因子将花费相当长的时间
现代加密技术就是运用此特性
7 楼
aozhouyang [专家分:0] 发布于 2010-04-09 12:38:00
6楼的说法有问题啊
比如 数为34 质因子为 17 和 2
其平方根小于6 按你的讲法 17 是求不出来的
8 楼
schopenkitto [专家分:0] 发布于 2010-09-26 22:34:00
program primefactor
implicit none
integer :: n, i
logical :: isPrime
do
print *, 'please input an integer'
read *, n
if(n == 0) exit
i = 2
do while(i<=n)
if( mod(n,i) == 0 ) then
print *, i
n = n/i
if(n == 1) then
exit
else
i = 2
endif
else
i=i+1
endif
enddo
enddo
end program
这样不用isprime过程的
9 楼
jstzhurj [专家分:4680] 发布于 2010-09-27 00:14:00
[quote]program primefactor
implicit none
integer :: n, i
logical :: isPrime
do
print *, 'please input an integer'
read *, n
if(n == 0) exit
i = 2
do while(i<=n)
if( mod(n,i) == 0 ) then
print *, i
n = n/i
if(n == 1) then
exit
else
i = 2
endif
else
i=i+1
endif
enddo
enddo
end program
这样不用isprime过程的
[/quote]
对楼上稍作修改,对于比较大的数,效率的提高还是比较明显的,不知妥否?
program primefactor
implicit none
integer(kind=8) :: i,j,k,n
do
print *, 'please input an integer'
read *, n
j = n
k = 1
if(j == 0) exit
i = 2
do while(i<=int(sqrt(real(j))))
if( mod(j,i) == 0 ) then
print *, i
k = k*i
j = j/i
if(j == 1) exit
else
i = i+1
endif
enddo
print *, n/k
enddo
end program
10 楼
jstzhurj [专家分:4680] 发布于 2010-09-27 00:19:00
有兴趣的网友可以验证,不妥之处,请不吝指正!
我来回复