fsieve.icl 1.38 KB
 Camil Staps committed Apr 02, 2018 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ``````module fsieve /* The Fast Sieve of Eratosthenes. A sequential and optimized version of the sieve of Eratosthenes. The program calculates a list of the first NrOfPrime primes. The result of the program is the NrOfPrimes'th prime. Strictness annotations have been added because the strictness analyser is not able to deduce all strictness information. Removal of these !'s will make the program about 20% slower. On a machine without a math coprocessor the execution of this program might take a (very) long time. Set NrOfPrimes to a smaller value. */ `````` Camil Staps committed Jun 11, 2019 18 ``````import StdEnv `````` Camil Staps committed Apr 02, 2018 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 `````` NrOfPrimes :== 3000 // The sieve algorithm: generate an infinite list of all primes. Primes :: [Int] Primes = pr where pr = [5:Sieve 7 4 pr] Sieve :: Int !Int [Int] -> [Int] Sieve g i prs | IsPrime prs g (toInt (sqrt (toReal g))) = [g:Sieve` g i prs] | otherwise = Sieve (g + i) (6 - i) prs Sieve` :: Int Int [Int] -> [Int] Sieve` g i prs = Sieve (g + i) (6 - i) prs IsPrime :: [Int] !Int Int -> Bool IsPrime [f:r] pr bd | f > bd = True | pr rem f==0 = False | otherwise = IsPrime r pr bd // Select is used to get the NrOfPrimes'th prime from the infinite list. Select :: [x] Int -> x Select [f:r] 1 = f Select [f:r] n = Select r (n - 1) /* The Start rule: Select the NrOfPrimes'th prime from the list of primes generated by Primes. */ Start :: Int Start = Select [2,3:Primes] NrOfPrimes``````