! ////////////////////////////////////////////////////////// ! // Name: Peter M. Maurer ! // Program: Sieve of Eratosthenes ! // Due: Never ! // Language: FORTRAN ! ///////////////////////////////////////////////////////// PROGRAM SieveE ! define the sieve data structure INTEGER Candidates(999); INTEGER i,j; DO 10 i=1 , 999 ! // everything is potentially prime until proven otherwise Candidates(i) = 1 10 CONTINUE ! // Neither 1 nor 0 is prime, so flag them off Candidates(1) = 0 ! // start the sieve with the integer 1 i = 1 DO WHILE (i .LT. 1000) ! // advance to the next un-crossed out number. ! // this number must be a prime DO WHILE (i .LT. 1000 .AND. Candidates(i) .EQ. 0) i = i+1 END DO ! // insure against running off the end of the data structure IF (i .LT. 1000) THEN ! // cross out all multiples of the prime, starting with 2*p. j = 2 DO WHILE (j*i .LT. 1000) Candidates(j*i) = 0 j = j + 1 END DO ! // advance to the next candidate i = i+1; ENDIF END DO ! // all uncrossed-out numbers are prime (and only those numbers) ! // print all primes DO 20 i=1 , 999 IF (Candidates(i) .NE. 0) THEN PRINT *,i," is prime"; ENDIF 20 CONTINUE END