toys/mathematics/number-theory/prime/primeFactors/largestPrimeFactor.f95

! ----------------------------------------------------------
! Programmer:   Jonathan Landrum
! Date:         5 September 2012
! ----------------------------------------------------------
! Program:      primeFactors.exe
! Purpose:      Calculates the largest prime factor of a
!               given number.
! Assumptions:  1.) Input from the user is in integer
!                   form. Text input will cause the
!                   program to fail. Real number input
!                   will be truncated into integers.
! ----------------------------------------------------------

PROGRAM primeFactors

	IMPLICIT NONE
	
	INTEGER,PARAMETER :: k32   = selected_int_kind(32)
	INTEGER(kind=k32) :: input = 0, factor, output
	LOGICAL           :: isPrime

	WRITE (*,*) '*************************************************'
	WRITE (*,*) '*                                               *'
	WRITE (*,*) '*    FORTRAN LARGEST PRIME FACTOR CALCULATOR    *'
	WRITE (*,*) '*                                               *'
	WRITE (*,*) '*************************************************'
	WRITE (*,*)
	WRITE (*,*) 'Copyright (c) 2012 Jonathan Landrum'
	WRITE (*,*)
	WRITE (*,*) 'Calculates the largest prime factor of a number.'
	WRITE (*,*) '-------------------------------------------------'
	WRITE (*,*)
	
	DO WHILE (input < 2)
		WRITE (*,'(a)',advance='no') ' Enter a number to calculate: '
		READ  (*,*) input
		WRITE (*,*)
	END DO
	
	factor = 2
	
	IF (isPrime(input)) THEN
		output = input
	ELSE
		DO WHILE (input .NE. factor)
			DO WHILE ((MOD(input,factor) == 0) .AND. (input .NE. factor))
				IF (input .NE. factor) THEN
					input = input / factor
				END IF
			END DO
			
			IF (input .NE. factor) THEN
				factor = factor + 1
				DO WHILE (isPrime(factor) .EQV. .FALSE.)
					factor = factor + 1
				END DO
			END IF
			
			output = factor
		END DO
	END IF
	
	WRITE (*,*) 'The largest prime factor is ', output
	WRITE (*,*)
	WRITE (*,*) '-------------------------------------------------'
	WRITE (*,*) '\\//_ Live long and prosper.'
END PROGRAM primeFactors

! ----------------------------------------------------------
! FUNCTION isPrime:
! Determines if the input is a prime number. Returns T or F.
! ----------------------------------------------------------
LOGICAL FUNCTION isPrime(n)
	IMPLICIT NONE
	
	INTEGER,PARAMETER :: k32 = selected_int_kind(32)
	INTEGER(kind=k32) :: n, i

	IF (n <= 1) THEN                    ! 1 is not prime
		isPrime = .FALSE.
	ELSE IF ((n == 2).OR.(n == 3)) THEN ! Hardcode 2 and 3
		isPrime = .TRUE.
	ELSE IF (MOD(n,2) == 0) THEN        ! Get rid of evens
		isPrime = .FALSE.

	! All other cases are out, so now we check to see if
	! n is divisible by the odd numbers from 3 on.
	ELSE
		i = 3
		isPrime = .TRUE.                             ! Assume it's prime, then prove
		DO                                           ! If i^2 is not a root of n, or if n%i = 0
			IF (i*i > n .OR. MOD(n,i) == 0) EXIT !(Won't be larger than the square)
			i = i + 2                            ! Iterate the counter by 2 to get odds
		END DO
		
		! Record the answer
		IF (i*i > n) THEN
			isPrime = .TRUE.
		ELSE
			isPrime = .FALSE.
		END IF
	END IF ! We have our answer
END FUNCTION isPrime