论文网
English Papers
万事OK网
发表论文
 
 首页 > IT文章 > 程序设计 >
森德拉姆素数筛法

[科技论文网] http://www.scipapers.com    2007-12-01  

    森德拉姆素数筛法

    大家看看下面的这个对称矩阵:

    4    7   10   13   16   19   22 ......

    7    12  17   22   27   32   37 ......

    10   17  24   31   38   45   52 ......

    13   22  31   40   49   58   67 ......

    16   27  38   49   60   71   82 ......

    ... ...

    规律是显然的:第一行首项为4,公差为3;第二行公差为5,...

    这个对称矩阵有什么用呢?

    这就是森德拉姆(Sundaram,1934)素数筛法矩阵,如果一个自然数N

    出现在矩阵当中,那么2*N+1是合数;相反,如果N不在表中出现,则

    2*N+1肯定是素数!

    这么神奇的矩阵,奥妙在哪里?

    其实原理很简单!

    让我们来分析一下:显然,矩阵的第i行、第j列的通项为

    2(i-1)(j-1)+3(i-1)+3(j-1)+4

    因此若N在表中的i行j列出现,则

    2*N+1=2(2(i-1)(j-1)+3(i-1)+3(j-1)+4)+1

    =(2(i-1)+3)(2(j-1)+3)

    显然是一个合数。

    假设2*N+1是合数,那么肯定存在奇数m,n满足2*N+1=m*n,并且

    m>=3,n>=3, 那么,

    N=(m*n-1)/2=((2*((m-3)/2)+3)(2*((n-3)/2)+3)-1)/2

    根据通项公式,N应该出现在矩阵的(m-3)/2+1行,(n-3)/2+1列。

    因此若N在表中不出现,则2*N+1必为素数!

    不足吗?还是有的!

    第一个素数2不知给筛到哪里去了。

    看来十全十美的东西很少啊!

        来源:

声明:本文由网友推荐或作者提交,版权归原作者所有,刊登此文仅为传播知识,展示研究成果,提高文章引用率。未经原作者授权,禁止用于任何形式的商业行为。科技论文网倡导尊重知识、尊重劳动、保护原创、知识共享。由于部分论文文章来于网络,文章作者不祥,请相关的原创作者与我们联系,以便加上您的署名。

  
森德拉姆素数筛法
下面没有链接了     一种快速图形拉伸算法
最新论文
·[程序设计]森德拉姆素数筛法
·[程序设计]一种快速图形拉伸算法
·[程序设计]扫描线种子填充算法
·[程序设计]C语言实现集合的交,并,差
·[程序设计]采用链式存储结构构造哈夫曼树
·[程序设计]链表反转的两种实现方法
·[程序设计]数据结构(C语言):迷宫问题
·[程序设计]"S/P先生数学谜题"算法分析及源代码
·[程序设计]单源最短路径bellman-ford算法
·[程序设计]前序遍历二叉树
 
 

搜索论文

Google
论文分类

论文网 论文发表网 论文 免费论文网 找论文网 毕业论文 中国论文网 英语论文 百度论文 聘教网 易搜
 免费发布论文    中国论文网 2008版权所有  业务联系:pinjiao@126.com