55 lines
1.5 KiB
Fortran
55 lines
1.5 KiB
Fortran
program totient_function
|
|
implicit none
|
|
integer, parameter :: M = 100000
|
|
integer :: i, j
|
|
integer, dimension(1:M) :: phi
|
|
character(len=10) :: is_prime
|
|
integer :: count100, count1000, count10000, count100000
|
|
|
|
! Initialize phi array
|
|
do i = 1, M
|
|
phi(i) = i
|
|
end do
|
|
|
|
! Compute totient using sieve method
|
|
do i = 2, M
|
|
if (phi(i) == i) then ! i is prime
|
|
do j = i, M, i
|
|
phi(j) = (phi(j) / i) * (i - 1)
|
|
end do
|
|
end if
|
|
end do
|
|
|
|
! Display for the first 25 integers
|
|
print*,'n phi prime'
|
|
print*,repeat('-',30)
|
|
do i = 1, 25
|
|
if (phi(i) == i - 1) then
|
|
is_prime = 'prime'
|
|
else
|
|
is_prime = 'not prime'
|
|
end if
|
|
print "(i0,t10,i3,t20,a)", i, phi(i), trim(is_prime)
|
|
end do
|
|
|
|
! Count primes up to specified limits
|
|
count100 = 0
|
|
count1000 = 0
|
|
count10000 = 0
|
|
count100000 = 0
|
|
do i = 2, M
|
|
if (phi(i) == i - 1) then
|
|
if (i <= 100) count100 = count100 + 1
|
|
if (i <= 1000) count1000 = count1000 + 1
|
|
if (i <= 10000) count10000 = count10000 + 1
|
|
count100000 = count100000 + 1
|
|
end if
|
|
end do
|
|
|
|
print *, 'Count of primes up to 100:', count100
|
|
print *, 'Count of primes up to 1,000:', count1000
|
|
print *, 'Count of primes up to 10,000:', count10000
|
|
print *, 'Count of primes up to 100,000:', count100000
|
|
|
|
end program totient_function
|