PROGRAM PRIMEFAC !Program: Lists all prime number factors for all natural numbers !from N1 to N2 (N1 and N2 are arbitrarily chosen). This code, !among other applications is useful for evaluation of timeseries !prior to Fast Fourier Transform (FFT) analysis. In FFT !analysis, prime number factors of a timeseries of length N !should be as small as possible for speed of computation. This !may be accomplished with a long timeseries by deleting or !repeating the last few series values (i.e., changing N by a !small amount). ! !Method used: Every composite (i.e., not prime) positive natural !number greater than one can be written as a product of prime !numbers which are each raised to a positive natural number !greater than or equal to one. The code also implements the !ancient "Sieve of Eratosthenes". The code first generates prime !numbers less than 3200 for factorization. Secondly, the code !generates and lists all of the prime number factors for each !individual consecutive natural number N from N1 to N2. The code !also implements a well known theorem in number theory: Every !composite number must have a prime number factor less than or !equal to the square root of the number itself. The value 3200 !below was chosen to easily cover the factorization of all !natural numbers less than or equal to 10,000,000 in this Fortran !code (i.e., sqrt(10,000,000) is about 3162.3). It is noted with !INTEGER*8 declaration below that the code can be re-written !(using a number larger than 3200) to factor composite numbers !much larger than 10,000,000. ! !Author: Dr. Jerry R. Ziemke INTEGER*8 P(3200),Q(3200),I,J,N,II,NLOOP II=0 WRITE(*,*) & 'This routine does a prime number factorization of all natural' WRITE(*,*) & 'numbers from a smallest number N1 to a largest number N2.' WRITE(*,*)'Enter beginning number N1 (1 < N1 <= 10,000,000): ' READ(*,*) X N1=IFIX(X) WRITE(*,*)'Enter largest number N2 (N1 <= N2 <= 10,000,000): ' READ(*,*) Y N2=IFIX(Y) WRITE(*,*)'Number N and its prime number factors:' WRITE(*,*)'--------------------------------------' !First generate all prime numbers less than 3200 - these !beginning prime numbers are used for factorization: DO I=1,3200 Q(I)=1 ENDDO DO I=2,40 IF (Q(I).EQ.1) THEN J=1 DO WHILE (I*J.LE.3200) Q(I*J)=0 J=J+1 ENDDO II=II+1 P(II)=I ENDIF ENDDO !Next generate and list all prime number factors for each !consecutive natural number N: DO NLOOP=N1,N2 N=NLOOP WRITE(*,'(1X,I8,A1)') N,':' DO I=1,II DO WHILE (MOD(N,P(I)).EQ.0) WRITE(*,*) P(I) N=IFIX(FLOAT(N)/FLOAT(P(I))) ENDDO IF ((N.NE.1).AND.(I.EQ.II)) THEN WRITE(*,*) N ENDIF ENDDO ENDDO STOP END