查找一组素数大于x的素数的算法 [英] algorithm to find products of a set of primes, in order, greater than x

问题描述

考虑有限集{2,3,5，...，n}。我对素数感兴趣，但这个问题可能适用于任何一组数字。我想找到这些数字升序的所有可能乘积，尤其是大于或等于某个数字x的乘积。有谁知道一个不错的算法吗？

编辑来澄清一下：

输入集中的每个因子都可能可以使用多次。如果输入为{2,3,5,7}，则输出为{2,3,4,5,6,7,8,9,10,12,14,15,16,18，...} 。该算法只要产生的结果大于或等于某个数字x，就可以立即停止。

解决方案

Haskell代码，如下所示在此答案中看到，

< pre class = lang-hs prettyprint-override> hamm :: [Integer]-> [整数]
hamm [] = []
hamm（p：ps）= xs-例如hamm [2,3,5]
其中xs = merge（hamm ps）-H（{p}∪ps）= S，
（p：map（p *）xs）-S ⊇{p}∪H（ps）∪{p * x | }

合并a @（x：xs）b @（y：ys）| x ＜ y = x：合并xs b
|否则= y：合并ys
合并[] b = b
合并a [] = a


合并此处不会尝试消除倍数，因为不会有倍数-仅在使用的情况下输入中的素数：

 〜>取20 $ hamm [2,3,5,7] 
 [2,3,4,5,6,7,8,9,10,12,14,15,16,18,20,21， 24,25,27,28] 
  

如果没有，则需要使用工会代替，

 工会a @（x：xs）b @（y：ys）| x ＜ y = x：联合xs b 
 | x> y = y：联合a ys 
 |否则= x：联合xs ys 
联合[] b = b 
联合a [] = a 
  

有效地从给定值开始（上）可能是一个有趣的挑战。在此答案底部的直接生成切片的代码可以作为起点。

通常，很容易跳过有序序列，直到传递值为止。在Haskell中，它是通过内置的 dropWhile（< n），

 〜>采取10 $下降而（<100）$ hamm [2,3,5,7] 
 [100,105,108,112,120,125,126,128,135,140] 
  

Consider the finite set {2,3,5,...,n}. I am interested in primes but the question could apply to any set of numbers. I want to find all possible products of these numbers in ascending order, and in particular greater than or equal to some number x. Does anyone know a nice algorithm for this?

EDIT to clarify:

Each factor in the input set may be used any number of times. If the input were {2,3,5,7} the output would be {2,3,4,5,6,7,8,9,10,12,14,15,16,18,...}. The algorithm can stop as soon as it produces a result greater than or equal to some number x.

解决方案

A Haskell code, as seen in this answer,

hamm :: [Integer] -> [Integer]
hamm []     = []   
hamm (p:ps) = xs        -- e.g. hamm [2,3,5] 
        where xs = merge (hamm ps)               --   H({p} ∪ ps) = S,
                         (p : map (p*) xs)       -- S ⊇ {p} ∪ H(ps) ∪ { p*x | x ∊ S }

merge a@(x:xs) b@(y:ys) | x < y     = x : merge xs b 
                        | otherwise = y : merge a ys 
merge [] b = b
merge a [] = a

merge here doesn't try to eliminate multiples, because there won't be any -- but only in case you're using only the primes in the input:

~> take 20 $ hamm [2,3,5,7]
[2,3,4,5,6,7,8,9,10,12,14,15,16,18,20,21,24,25,27,28]

If not, you need to use union instead,

union a@(x:xs) b@(y:ys) | x < y     = x : union xs  b
                        | x > y     = y : union a  ys
                        | otherwise = x : union xs ys
union [] b = b
union a [] = a

Starting from (above) a given value efficiently might be an interesting challenge. A directly slice-generating code at the bottom of this answer could be taken as a starting point.

In general it is easy to skip along the ordered sequence until a value is passed over. In Haskell, it is done with a built-in dropWhile (< n),

~> take 10 $ dropWhile (< 100) $ hamm [2,3,5,7]
[100,105,108,112,120,125,126,128,135,140]

这篇关于查找一组素数大于x的素数的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！