-
Notifications
You must be signed in to change notification settings - Fork 1
/
214.f90
44 lines (34 loc) · 936 Bytes
/
214.f90
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
program totient_chain
implicit none
integer :: ii
write (*,*) "GCD of 5, 10", GCD(5, 10)
write (*,*) "GCD of 36, 78", GCD(36, 78)
do ii=1,20
write (*,*) ii, TotientChain(ii)
end do
contains
recursive function GCD(a, b) result(n)
integer :: a, b, n
if (b .eq. 0) then
n = a
else
n = GCD(b, mod(a, b))
end if
end function GCD
function Totient(n)
integer :: n, Totient
integer :: k
Totient = 0
do k = 1, n
if (GCD(k, n) .eq. 1) Totient = Totient + 1
end do
end function Totient
recursive function TotientChain(start) result(chainLen)
integer :: start, chainLen
if (start .eq. 1) then
chainLen = 1
else
chainLen = 1 + TotientChain(Totient(start))
end if
end function TotientChain
end program totient_chain