0

使用しようとしているコードは次のとおりです。これにより、最大 100 までのすべての素数が生成されます。

sieve_primes = [x | x<-[2..100], y<-[2..50], z <-[2..25], (x*z) `mod` y /= 0]
4

2 に答える 2

0

あなたが考えていたのは、おそらく

Prelude> [x| x<-[2..100], not $ elem x [y*z| y<-[2..50], z<-[2..25]]]
[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]

これは非常に遅いです。少なくとも、ピースを並べ替えることができます。

Prelude> [x| let sieve=[y*z| y<-[2..50], z<-[2..25]], 
             x<-[2..100], not $ elem x sieve]
[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]

1000 をはるかに超える数値 (500 と 250 を使用する場合) では、これは依然として非常に低速です。繰り返しになりますが、なぜ 25 (250) 制限なのですか? あなたのコードは

primes = [x| x<-[2..], not $ elem x 
                       [y*z| y<-[2..x`div`2], z<-[2..min y (x`div`y)]]]

つまりy*z = 2*y .. min (y*y) x、既知の上限 ( x <= n) を使用すると、次のようになります。

primesTo n = [x| let sieve=[y*z| y<-[2..n`div`2], z<-[2..min y (n`div`y)]],
                 x<-[2..n], not $ elem x sieve]

(ちなみに、max (min y (n/y)) {y=2..n/2} = sqrt nなので、25 の代わりに 10 を使用することもできました (1000 の場合は 250 の代わりに 31 を使用できます))。

現在、1000 は問題ではありません。~ 10,000 を超えると、(まだ) 遅いことが再びわかり始め、n 2.05..2.10 で実行され、経験的な成長のオーダー( n = 5000、10000、15000で GHCi で解釈されたコードをすばやくテストします) .

2番目の（現在は削除された）関数については、次のように、速度を段階的に改善しながら書き直すことができます。

isPrime n = length [x | x<-[2..n], n `mod` x == 0] == 1
          = take 1 [x | x<-[2..n], n `mod` x == 0] == [n]
          = [x | x<- takeWhile ((<=n).(^2)) [2..n], n `mod` x == 0] == []
          = and [n `mod` x > 0 | x<- takeWhile ((<=n).(^2)) (2:[3,5..n])]

コンパイルされた今では、最初の 10,000 個の素数を数十分の一秒で取得できます。

于 2014-11-11T08:28:12.560 に答える