Eratosthenes真正的筛 - 用于生成素数的算法 [英] The Genuine Sieve of Eratosthenes -- algorithm used to generate prime numbers

查看:142
本文介绍了Eratosthenes真正的筛 - 用于生成素数的算法的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

今天我读了一篇论文:


O'Neill,Melissa E.,真正的
Eratosthenes的筛子,
Journal of
函数式编程,已发布
online by Cambridge University Press
2008年10月9日
doi:10.1017 / S0956796808007004。

使用优先级队列生成素数的算法:

$ $ $ $ $ $ $ $ $ $ $ $>筛号[] = []
筛号(x:xs )= x:sieve'xs(insertprime x xs PQ.empty)
其中
insertprime p xs table = PQ.insert(p * p)(map(* p)xs)table
sieve'[] table = []
sieve'(x:xs)table
| nextComposite< = x = sieve'xs(调整表格)
|否则= x:sieve'xs(insertprime x xs表)
其中
nextComposite = PQ.minKey表
调整表
| n< = x = adjust(PQ.deleteMinAndInsert n'ns表)
|否则=表
其中
(n,n':ns)= PQ.minKeyValue表

素数= sieve [2 ..]

该算法乍一看似乎是正确的,但我不明白一件事:



PQ如何使用句柄重复最小优先级?



我手工进行了一些模拟,发现可能会导致错误。



如果有人能解释它,我将非常感谢您的帮助!

解决方案

这篇文章提到了正在使用的优先级队列:


考虑到这些需求,优先级队列
是一个有吸引力的选择,特别是因为这个数据结构原生支持多个具有相同优先级的
项目(以任意顺序出列)。

由于重复的条目在他们拥有的算法中并不真正有用e将被特别处理。

调整函数删除最小合成,不断调整优先级队列直到可以肯定的是,最小元素的所有重复项都被删除:

 调整表
| n< = x = adjust(PQ.deleteMinAndInsert n_ns表)
|否则=表
其中...

如果当前第一个元素( n )足够小,可以被移除,再次调整自身以检查剩余队列中的下一个元素。只有当没有小元素时,它才会停止递归。


Today I read a paper:

O'Neill, Melissa E., "The Genuine Sieve of Eratosthenes", Journal of Functional Programming, Published online by Cambridge University Press 09 Oct 2008 doi:10.1017/S0956796808007004.

It described an algorithm of generating prime number by using Priority Queue :

sieve [] = []
sieve (x:xs) = x : sieve' xs (insertprime x xs PQ.empty)
    where
        insertprime p xs table = PQ.insert (p*p) (map (* p) xs) table
        sieve' [] table = []
        sieve' (x:xs) table
            | nextComposite <= x = sieve' xs (adjust table)
            | otherwise = x : sieve' xs (insertprime x xs table)
            where
                nextComposite = PQ.minKey table
                adjust table
                    | n <= x = adjust (PQ.deleteMinAndInsert n' ns table)
                    | otherwise = table
                    where
                        (n, n':ns) = PQ.minKeyValue table

primes = sieve [2 .. ]

The algorithm seems to be correct at first glance, but I don't understand one thing:

How does the PQ it uses handle duplicated minimal priority?

I made some simulation by hand and I found that might cause an error.

If some one could explain it, I will appreciate your help!

解决方案

The paper says this about the priority queue that is being used:

Given these needs, a priority queue is an attractive choice, especially since this data structure natively supports multiple items with the same priority (dequeuing in them arbitrary order).

Since duplicate entries are not really useful in the algorithm they have to be treated specially.

The adjust function, which removes the minimal composite, keeps adjusting the priority queue until it can be sure that all duplicates of the minimal element are removed:

adjust table
    | n <= x = adjust (PQ.deleteMinAndInsert n_ ns table)
    | otherwise = table
    where ...

If the currently first element (n) was small enough to be removed, adjust calls itself again to also check the next element in the remaining queue. Only when there are no small elements left it stops recursing.

这篇关于Eratosthenes真正的筛 - 用于生成素数的算法的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆