home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 7 / Apprentice-Release7.iso / Environments / Clean 1.2.4 / Small Demos / fsieve.icl < prev    next >
Encoding:
Text File  |  1995-03-10  |  1.4 KB  |  54 lines  |  [TEXT/3PRM]
  1. module fsieve
  2.  
  3. /*
  4. The Fast Sieve of Eratosthenes.
  5.  
  6. A sequential and optimized version of the sieve of Eratosthenes.
  7. The program calculates a list of the first NrOfPrime primes.
  8. The result of the program is the NrOfPrimes'th prime.
  9.  
  10. Strictness annotations have been added because the strictness analyser
  11. is not able to deduce all strictness information. Removal of these !'s
  12. will make the program about 20% slower.
  13.  
  14. On a machine without a math coprocessor the execution of this
  15. program might take a (very) long time. Set NrOfPrimes to a smaller value.
  16. */
  17.  
  18. import StdClass; // RWS
  19. import StdInt, StdReal
  20.      
  21. NrOfPrimes :== 3000 
  22.     
  23. //    The sieve algorithm: generate an infinite list of all primes.
  24.  
  25. Primes::[Int]
  26. Primes = pr where pr = [5 : Sieve 7 4 pr]
  27.  
  28. Sieve::Int !Int [Int] -> [Int]
  29. Sieve g i prs
  30.     | IsPrime prs g (toInt (sqrt (toReal g)))    =  [g : Sieve` g i prs]
  31.                                                 =  Sieve (g + i) (6 - i) prs
  32.  
  33. Sieve`::Int Int [Int] -> [Int]
  34. Sieve` g i prs =  Sieve (g + i) (6 - i) prs
  35.  
  36. IsPrime::[Int] !Int Int -> Bool
  37. IsPrime [f:r] pr bd | f>bd             =  True
  38.                     | pr mod f==0    =  False
  39.                                     =  IsPrime r pr bd
  40.                                   
  41. //    Select is used to get the NrOfPrimes'th prime from the infinite list.
  42.  
  43. Select::[x] Int -> x
  44. Select [f:r] 1 =  f
  45. Select [f:r] n =  Select r (n - 1)
  46.  
  47.  
  48. /*    The Start rule: Select the NrOfPrimes'th prime from the list of primes
  49.     generated by Primes.
  50. */
  51.  
  52. Start::Int
  53. Start = Select [2, 3 : Primes] NrOfPrimes
  54.