The sieve of Sundaram: Difference between revisions
Content added Content deleted
Line 278: | Line 278: | ||
=={{header|Fortran}}== |
=={{header|Fortran}}== |
||
<lang Fortran> |
<lang Fortran> |
||
PROGRAM SUNDARAM |
|||
Something |
|||
IMPLICIT NONE |
|||
! |
|||
! Local variables |
|||
! |
|||
INTEGER(8) :: curr_index |
|||
INTEGER(8) :: i |
|||
INTEGER(8) :: j |
|||
INTEGER :: lim |
|||
INTEGER(8) :: mid |
|||
INTEGER :: primcount |
|||
LOGICAL*1 , ALLOCATABLE , DIMENSION(:) :: primes !Array of booleans representing integers |
|||
lim = 10000000 ! Not the number of primes but the storage where the prime marker is held for the millionth prime |
|||
ALLOCATE(primes(lim)) |
|||
primes(1:lim) = .TRUE. |
|||
!Set all to .True., we will later block out the known non-primes |
|||
mid = lim/2 |
|||
!Generate primes |
|||
DO j = 1 , mid |
|||
DO i = 1 , j |
|||
curr_index = i + j + (2*i*j) |
|||
IF( curr_index>lim )EXIT ! Too big already, leave the loop. |
|||
primes(curr_index) = .FALSE. !This candidate will not produce a prime |
|||
END DO |
|||
END DO |
|||
!Find first number still prime below lim |
|||
i = 0 |
|||
j = 0 |
|||
WRITE(6 , *)'The first 100 primes:' |
|||
DO WHILE ( i < 100 ) |
|||
j = j + 1 |
|||
IF( primes(j) )THEN |
|||
WRITE(6 , 34 , ADVANCE = 'no')j*2 + 1 !Take the candidate, multiply by 2, add 1, and you have a prime |
|||
34 FORMAT(I0 , 1x) |
|||
i = i + 1 ! Counter used for printing |
|||
IF( MOD(i,10)==0 )WRITE(6 , *)' ' |
|||
END IF |
|||
END DO |
|||
! Now print the millionth prime |
|||
primcount = 0 |
|||
DO i = 1 , lim |
|||
IF( primes(i) )THEN |
|||
primcount = primcount + 1 |
|||
IF( primcount==1000000 )THEN |
|||
WRITE(6 , 35)'1 millionth Prime Found: ' , (i*2) + 1 |
|||
35 FORMAT(/ , a , i0) |
|||
EXIT |
|||
END IF |
|||
END IF |
|||
END DO |
|||
DEALLOCATE(primes) |
|||
STOP |
|||
END PROGRAM SUNDARAM |
|||
</lang> |
</lang> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
The first 100 primes: |
|||
3 |
|||
3 5 7 11 13 17 19 23 29 31 |
|||
37 41 43 47 53 59 61 67 71 73 |
|||
79 83 89 97 101 103 107 109 113 127 |
|||
131 137 139 149 151 157 163 167 173 179 |
|||
181 191 193 197 199 211 223 227 229 233 |
|||
239 241 251 257 263 269 271 277 281 283 |
|||
293 307 311 313 317 331 337 347 349 353 |
|||
359 367 373 379 383 389 397 401 409 419 |
|||
421 431 433 439 443 449 457 461 463 467 |
|||
479 487 491 499 503 509 521 523 541 547 |
|||
1 millionth Prime Found: 15485867 |
|||
</pre> |
</pre> |
||