这是基于我上面评论的一些代码：我们将运行 Eratosthenes 筛，但在我们执行此操作时，会存储一些额外的数据，而不仅仅是“素数或非素数”。它在 Haskell 中，我认为这不是最常用的语言，所以我将内联评论每一位的作用。首先是一些库导入：
import Control.Monad
import Control.Monad.ST
import Data.Array.ST
import Data.Maybe
我们将定义一个新类型 ，Primality我们将使用它来存储每个数字的最多两个素数。
data Primality
= Prime
| OneFactor Integer
| TwoFactor Integer Integer
| ManyFactor
deriving (Eq, Ord, Read, Show)
这表示有四种类型的值Primality：要么是值Prime，要么是值，要么是OneFactor n某个无界整数的形式值，要么是两个无界整数n的形式值和，或者是值。所以这有点像一个最多两个整数长的 s 列表（或者一个说明它是三个整数或更长的注释）。我们可以将因子添加到这样的列表中：TwoFactor n n'nn'ManyFactorInteger
addFactor :: Integer -> Primality -> Primality
addFactor f Prime = OneFactor f
addFactor f (OneFactor f') = TwoFactor f f'
addFactor _ _ = ManyFactor
给定一个数的质因数列表，很容易检查它是否是半质数：它最多必须有两个较小的质因数，其乘积就是数本身。
isSemiprime :: Integer -> Primality -> Bool
isSemiprime n (OneFactor f ) = f * f == n
isSemiprime n (TwoFactor f f') = f * f' == n
isSemiprime _ _ = False
现在我们将编写 Sieve。根据 Bertrand 的假设，对于任何，在和n之间都有一个素数；这意味着在和之间有一个半素数（即假设给我们的素数的两倍）。更重要的是，任何这样的半素数都不能有一个大于的因子（因为那时另一个因子必须小于！）。因此，我们将根据 至的因子筛选 至 的数字，然后检查 和 之间的数字是否为半素数。因为后一种检查是 O(1)，所以我们属于您提出的第一种情况。所以：n/2nn2nn22nnn2n
nextSemiprime :: Integer -> Integer
nextSemiprime n = runST $ do
2创建一个索引在和之间的数组，在每个位置2n初始化。Prime
arr <- newSTArray (2,2*n) Prime
对于和...p之间的每个潜在素数2n
forM_ [2..n] $ \p -> do
...我们目前认为是Prime...
primality <- readArray arr p
when (primality == Prime) $
...为 的每个倍数添加p到因子列表中p。
forM_ [2*p,3*p..2*n] $ \i ->
modifyArray arr i (addFactor p)
现在对半素数之间的剩余数字进行线性n+1搜索2n。每次调用都isSemiprime需要一个乘法，所以它们是 O(1)。从技术上讲，搜索可能会失败；fromJust <$>注释告诉编译器我们保证它不会失败（因为我们已经完成了一些离线数学证明，这些证明太复杂而无法传输给编译器）。
fromJust <$> findM (\i -> isSemiprime i <$> readArray arr i) [n+1..2*n]
那是整个身体nextSemiprime。它使用了一些真正应该在某个地方的标准库中的辅助函数。首先是线性搜索算法；它只是沿着列表查找满足谓词的元素。
findM :: Monad m => (a -> m Bool) -> [a] -> m (Maybe a)
findM f [] = return Nothing
findM f (x:xs) = do
done <- f x
if done then return (Just x) else findM f xs
该modifyArray函数只是读取一个数组元素并写回修改后的版本。arr[ix] = f(arr[ix]);在 C 中思考。
modifyArray :: (MArray a e m, Ix i) => a i e -> i -> (e -> e) -> m ()
modifyArray arr ix f = readArray arr ix >>= writeArray arr ix . f
由于 Haskell 对数组的处理方式变幻莫测，因此newSTArray需要它：所有数组操作在您使用的数组类型上都是多态的，这既方便又烦人。这告诉编译器我们想要这个程序使用哪种类型的数组。
newSTArray :: Ix i => (i,i) -> e -> ST s (STArray s i e)
newSTArray = newArray
您可以在这里尝试一下，其中包括一个简单main的打印前 100 个半素数的方法。（尽管如果这是目标，后一项任务可以以更有效的方式完成！）
尽管当前算法只返回下一个半素数，但很容易修改它以返回下一个半素数的分解：只返回关联Primality值而不是Integer本身。