推荐视频:另类素数筛选法

  

    画一个三角形阵列,初始时只有每一行的两头有标记,然后从上到下依次把每一行复制两份,摆放成一个等边三角形。最后你会发现,第i行为空行(除两头外不再有其它标记),当且仅当i为素数。对于其它行,标记的位置也与该行行号的质因子有关。这是为什么呢?
    照惯例,给个YouTube链接:http://youtube.com/watch?v=sbjPwyPT1AI

    设f[i,j]表示第i行左起第j个位置是否有标记。j从0开始计数(即第i行最左边用f[i,0]表示)。对于每个f[i,j],我们将它的值赋给了f[i+j,j]和f[2*i-j,i]。也就是说,对于每组i和j,我们都进行以下两个操作:
f[i+j,j] <- f[i,j]
f[2*i-j,i] <- f[i,j]
    而这实际上就是辗转相除的变形,不断递归下去后,最终f[i,j]表示的其实就是i和j是否互质。这样一来,上面那些东西就全解释清楚了。
    用这种方法描述数论问题是一件很有趣的事,给人感觉很神奇。如果你感兴趣的话,这里有一个类似的例子,你可以看到Sierpinski三角形、杨辉三角和组合数的奇偶性是如何联系在一起的。

7 条评论

发表评论

  +  36  =  44