标签: wheel-factorization

当按照维基百科上的轮分解过程进行操作时，我似乎无意中遇到了一个问题：如果我尝试构建 2-3-5-7 轮，则素数 331 被视为合数。

采用2-3-5-7轮，2*3*5*7=210。因此，我设置了一个包含 210 个槽位的圆圈，并顺利完成步骤 1-7。然后我进入第8步，划掉所有素数倍数的辐条，最终划掉以121为根的辐条，121是11的倍数，11是素数。对于以 121 为根的辐条，121 + 210 = 331。不幸的是，331 是一个质数。

维基百科上的程序不正确吗？

或者我是否误解了该过程，应该只删除 2、3、5 和 7 的倍数的辐条，而不删除任何小于 210 的其他素数？

我正在从这里修改Eratosthenes的无限筛子,所以它使用轮子分解来跳过更多的复合材料而不是当前检查所有可能性的形式.

我已经弄清楚如何生成步骤以达到车轮上的所有间隙.从那里我想我可以用+ 2代替这些轮子步骤,但它导致筛子跳过素数.这是代码:

from itertools import count, cycle

def dvprm(end):
    "finds primes by trial division. returns a list"
    primes=[2]
    for i in range(3, end+1, 2):
        if all(map(lambda x:i%x, primes)):
            primes.append(i)
    return primes

def prod(seq, factor=1):
    "sequence -> product"
    for i in seq:factor*=i
    return factor

def wheelGaps(primes):
    """returns list of steps to each wheel gap
    that start from the last value in primes"""
    strtPt= primes.pop(-1)#where the wheel starts
    whlCirm= prod(primes)# wheel's circumference

    #spokes are every number that are divisible …

作为一些欧拉苦难的一部分,我正试图用分解轮编码一个Eratosthenes的筛子.到目前为止我的代码是:

(defun ring (&rest content)
"Returns a circular list containing the elements in content.
 The returned list starts with the first element of content."
   (setf (cdr (last content)) content))

(defun factorization-wheel (lst)
"Returns a circular list containing a factorization 
 wheel using the list of prime numbers in lst"
   (let ((circumference (apply #'* lst)))
     (loop for i from 1 to circumference
           unless (some #'(lambda (x) (zerop (mod i x))) lst)
             collect i into wheel
           finally …