Решето Эратосфена выполняется слишком долго

@flammberg · Регистрация: 20.08.2012

Author24 — интернет-сервис помощи студентам

Следующий код...

Haskell

eratosPrimes :: Int -> [Int]
eratosPrimes n = getEratosPrimes n [] [2..]
    where
        getEratosPrimes :: Int -> [Int] -> [Int] -> [Int]
        getEratosPrimes n result (first:rest) | (length result) >= n = result
                | otherwise = getEratosPrimes n (result ++ [first]) $ [p | p <- rest, not (p `elem` [first * 2, first * 3..])]

...уже при n = 2 выполняется слишком долго (но все же выполняется). Что тут можно или нужно изменить?

@Mysterious Light · 26.10.2012, 23:54

Сообщение от flammberg

Haskell

1	not (p `elem` [first * 2, first * 3..])

Я бы побоялся использовать такую конструкцию. А что если p и вправду не будет элементом этого списка, то есть (p `rem` first) == 0? Эта проверка вообще не остановится. Пробовал запустить для n=3 и выше?
Замени её на явную проверку.

Haskell

eratosPrimes :: Int -> [Int]
eratosPrimes n = getEratosPrimes n [] [2..]
 
getEratosPrimes :: Int -> [Int] -> [Int] -> [Int]
getEratosPrimes n result (first:rest)
    | (length result) >= n  = result
    | otherwise             = getEratosPrimes n (result ++ [first]) $ 
        [p | p <- rest, (p `rem` first) /= 0 ]

А ещё лучше использовать функцию filter, ИМХО, будет понятнее.

@calabi-yau · 27.10.2012, 00:05

Сообщение от flammberg

...уже при n = 2 выполняется слишком долго (но все же выполняется). Что тут можно или нужно изменить?

length result и вставка в конец result ++ [first], но это мелочи.
Тормоз тут not (p `elem` [first * 2, first * 3..]) - проход по всему списку, который теоретически бесконечен (для Integer например), но для Int нет. Переписать можно так:

Haskell

1
2
3

primes' n = take n $ sieve [2 .. ] 
  where
    sieve (x:xs) = x : [k | k <- xs, k `mod` x /= 0]

@flammberg · 27.10.2012, 00:29 **[ТС]**

Mysterious Light, да, вот так работает хорошо.

@Catstail · 27.10.2012, 20:56

Простенькое решето Эратосфена:

Haskell

-- Удаление из списка заданного числа и всех его кратных
 
delK :: [Integer] -> Integer -> [Integer]
delK [] _ = []
delK (x:xs) y  | ((x `mod` y == 0) && (x > y)) = delK xs y
               | otherwise =   x:(delK xs y)
 
-- Решето Эратосфена (с накапливающими параметрами)
 
sieve' :: [Integer] -> Integer -> Integer -> [Integer]
sieve' x n k = if (k >= (floor . sqrt . fromInteger) n) then x
               else sieve' (delK x k) n (k+1)
 
-- "Парадная" функция
 
sieve :: Integer -> [Integer]
sieve m = sieve' [1..m] m 2
 
 
Main> sieve 100
[1,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]

@flammberg · 27.10.2012, 21:05 **[ТС]**

Catstail, вы написали функцию для вычисления всех простых чисел, меньших заданного. Я же - для вычисления первых n простых чисел.

Кроме того, мне кажется, что вот это неравенство...

Haskell

1	k >= (floor . sqrt . fromInteger) n

...должно быть строгим. То есть, к должно быть строго больше корня из n.

@Catstail · 27.10.2012, 22:13

Так поиск простых чисел, меньших n и есть по определению решето Эратосфена. Ваша задача сложнее...

Добавлено через 33 минуты
А вот "детское" решение задачи о списке простых чисел:

Haskell

isPrime' :: Int -> Int -> Bool
isPrime' x m | (m > (floor . sqrt . fromInt) x) = True 
             | otherwise = ((x `mod` m) /= 0) && (isPrime' x (m+1))  
 
isPrime :: Int -> Bool
isPrime x = isPrime' x 2
             
primeList' :: Int -> Int -> [Int] -> [Int]
primeList' n m x | length x == n = x
                 | otherwise = if (isPrime m) then primeList' n (m+1) (m:x)
                                 else primeList' n (m+1) x 
                                 
primeList :: Int -> [Int]
primeList n = primeList' n 2 []
 
Main> primeList 100
[541,523,521,509,503,499,491,487,479,467,463,461,457,449,443,439,433,431,421,419
,409,401,397,389,383,379,373,367,359,353,349,347,337,331,317,313,311,307,293,283
,281,277,271,269,263,257,251,241,239,233,229,227,223,211,199,197,193,191,181,179
,173,167,163,157,151,149,139,137,131,127,113,109,107,103,101,97,89,83,79,73,71,6
7,61,59,53,47,43,41,37,31,29,23,19,17,13,11,7,5,3,2]

Добавлено через 5 минут

Сообщение от calabi-yau

primes' n = take n $ sieve [2 .. ] where sieve (x:xs) = x : [k | k <- xs, k `mod` x /= 0]

- или я чего-то не понял, но попадаются и составные числа:

Haskell

primes' n = take n $ sieve [2 .. ] 
  where
    sieve (x:xs) = x : [k | k <- xs, k `mod` x /= 0]
 
Main> primes' 10
[2,3,5,7,9,11,13,15,17,19]

@calabi-yau · 27.10.2012, 22:54

Сообщение от Catstail

или я чего-то не понял, но попадаются и составные числа:

да, ошибка

Haskell

1	sieve [k \| k <- xs, k `mod` x /= 0]

конечно.

@flammberg 17 / 7 / 0 Регистрация: 20.08.2012 Сообщений: 51
	27.10.2012, 00:29 [ТС]	4
	Mysterious Light, да, вот так работает хорошо. 0

	27.10.2012, 22:54