当前位置:天才代写 > tutorial > 大数据教程 > 素数判定算法

素数判定算法

2021-02-17 12:09 星期三 所属: 大数据教程 浏览:14

1. 素数判断难题

素数判断难题是一个十分普遍的难题,文中详细介绍了常见的几类判断方式。

2. 初始优化算法

素数的定义是,除开能被1和它自身整除而不可以被别的任何数整除的数。依据素数界定 只必须用2到n-1除去n,假如都除不尽,则n是素数,不然,只需在其中有一个数能整除则n并不是素数。

bool is_primer1(int num) {
  int i;
  for(i = 2; i < num; i  ) {
   if(num % i == 0)  {
      return true;
    }
  }
  return false;
}

3. 改善优化算法

n并不是素数,则n可表明为a*b,其中2<=a<=b<=n-1,则a,b中必有一个数考虑:1<x<=sqrt(n),因此,只必须用2~sqrt(n)除去n,那样就获得一个复杂性为O(sqrt(n))的优化算法

bool is_primer2(int num) {
  int i;
  int upper = sqrt(num);
  printf("primer2:%d\n", upper);
  for(i = 2; i <= upper; i  ) {
    if(num % i == 0) {
      return true;
    }
  }
  return false;
}

4. 挑选优化算法

更高效率地素数判断方式应该是将素数事先储存到一个素数表中,当分辨一个数是不是为素数时,立即查询表就可以。这类方式必须处理2个难题:

(1) 怎样快速获得素数表?(选用挑选方式)

(2) 如何降低素数表的尺寸?(选用位图文件算法设计)

针对1到n所有整数金额,逐一分辨他们是不是素数,找到一个非素数,就把它挖去,最终剩余的便是素数。具体做法是:

<1> 界定is_primer[i] = true;

<2> 从4开始,先后解析xml全部is_primer(直至sqrt(N)),假如is_primer[i]=true,则is_primer[n*i]=false

如1,2,3,4,5,6,7,8,9,10,则

从4开始解析xml:

is_primer[2]=true,则is_primer[4]= is_primer[6]= is_primer[8]= is_primer[10]= true

is_primer[3]=true,则is_primer[6]= is_primer[9]= true

为了更好地降低运行内存利用率,优化算法应用了位图文件算法设计,有关位图文件,可参照:http://dongxicheng.org/structure/bitmap/

bool load_primer_table1() { //储存素数表
  int i;
  for(i = 1; i < INT_MAX; i  ) {
    if(i % 2 != 0 //双数一定并不是素数
      && is_primer2(i)) {
      set(i);
    }
  }
}
bool load_primer_table2() {//另一种迅速的方式储存素数表
  int i, j;
  for(i = 1; i <= INT_MAX; i  ) { 
    if( i % 2) { 
      set(i); 
    } else {
      clear(i);
    }
  }
  int upper = sqrt(INT_MAX);
  for(i = 1; i <= upper; i  ) {
    if(test(i)) {
      for(j = i   i; j < INT_MAX; j  = i)
        set(i);
    }
  }
}
bool is_primer3(long num) { //查询表分辨是不是为素数
  if(test(num))
    return true;
  return false;
}

5. 提升的挑选优化算法

(1) 储存方法提升

依然选用位图文件方法储存,只不过位图文件中只储存合数,那样一下子节约了一半室内空间(必须的室内空间仅为4g/(32*2)=64MB)

储存空间提升后,优化算法高效率也会提高许多 ,如:1,2,…,30

只需储存3,5,7,9,11,13,15,17,19,21,23,25,27,29

i=0, is_primer[0] =true, 把字符[3][6][9][12],即9,15,21,27,标成false

i=1, s_primer[0] =true,把字符为[6][11],即15,25标成false

i=2, 2*i 3>sqrt(30),完毕

即:i=s, 把字符为s(2*t 1) 3t,在其中,t=1,2,3,…中全部的的is_primer置为false

(2) 提升筛选优化算法

a是素数,则下一个起始点是a*a,把后边的全部的a*a 2*i*a筛除。即贪求n之内的素数,就先把sqrt(n)内的素数求出去,用早已求取的素数来筛选后边的合数。

6. 小结

迄今截止,沒有所有人发觉素数的遍布规律性,也没人能用一个计算公式出全部的素数。有关素数的许多 的有意思的特性或是生物学家的勤奋,如:

(1) 高斯函数猜想,n之内的素数数量大概与n/ln(n)非常,换句话说,当n非常大时,二者量级同样。这就是知名的素数定理。

(2) 十七世纪费马猜想,2的2^n三次方 1,n=0,1,2…时是素数,那样的数叫费马素数,遗憾当n=5时,2^32 1就并不是素数,迄今都没有寻找第六个费马素数。

(3) 18世纪发觉的最大素数是2^31-1,十九世纪发觉的最大素数是2^127-1,二十世纪末人们已经知道的最大素数是2^859433-1,用十进制表明,这是一个258715位的数据。

(4) 孪生素数猜测:差为2的素数有无限多对。现阶段了解的较大 的孪生素数是1159142985×2^2304-1和1159142985×2^2304+1。

(5) 歌德巴赫猜想:超过2的全部双数均是2个素数的和,超过5的全部合数均是三个素数之和。在其中第二个猜测是第一个的当然推理,因而歌德巴赫猜想又被称作1 1难题。我国数学家陈景润证实了1 2,即全部超过2的双数全是一个素数和仅有2个素数因素的合数的和。国际性上称之为陈氏定理。(节选自《http://chuanbindeng.blog.163.com/blog/static/67886226200982892139468/》)

7. 参考文献

http://www.doc88.com/p-5780302974.html

http://chuanbindeng.blog.163.com/blog/static/67886226200982892139468/

 

    关键字:

天才代写-代写联系方式