首先贴以下梅森素数的百度百科,科普下梅森素数是什么

梅森素数是由梅森数而来。
所谓梅森数,是指形如2p-1的一类数,其中指数p是素数,常记为Mp 。如果梅森数是素数,就称为梅森素数。
用因式分解法可以证明,若2p-1是素数,则指数p也是素数;反之,当p是素数时,2p-1(即Mp)却未必是素数。前几个较小的梅森数大都是素数,然而梅森数越大,梅森素数也就越难出现。
目前仅发现50个梅森素数,最大的是 277232917-1(即2的77232917次方减1),有23249425位数。

 

简单来说,梅森素数公式就是

2^p -1 = Mp

p为素数时 Mp为梅森数

若Mp也为素数时 , 2^p - 1 为梅森素数

 

下面这段代码是我以前闲的时候用java实现的简易梅森素数算法

单线程,所以效率并不高,算到2^19之后再算出梅森素数的效率就明显变慢,后来打算用多线程实现也一直就搁置了,以后有机会再研究。

  1. package test;
  2.  
  3. import java.util.ArrayList;
  4. import java.util.List;
  5.  
  6. /**
  7.  * bumblebee 2017-09-12
  8.  * 梅森素数公式 : 2^p -1 = Mp p为素数时 Mp为梅森数 若Mp也为素数时 , 2^p - 1 为梅森素数
  9.  */
  10. public class T2 {
  11. /**
  12.  * 传入计算范围最大值LONG l,排除法找出范围内梅森素数并输出
  13.  */
  14. public static void getSushu(Long l) {
  15. List<Long> list = new ArrayList<Long>();
  16. int c = 1;
  17. x: for (long i = 2; i < l; i++) {
  18. for (int j = 0; j < list.size(); j++) {
  19. // i能被list中的数字整除则跳出循环
  20. if (% list.get(j) == 0)
  21. continue x;
  22. }
  23. //不能被比自己小的所有素数整除的数字必是一个素数,装入list
  24. list.add(i);
  25. //到这里再继续判断这个素数是否梅森素数 与比自己小的所有的素数过一遍公式,配上就是梅森素数,如果超过i的大小则不用继续
  26. for (int j = 0; j < list.size(); j++) {
  27. if (Math.pow(2, list.get(j)) - 1 == i) {
  28. System.out.println(c++ + "\t2^" + list.get(j) + "-1\t=\t" + i);
  29. } else if (Math.pow(2, list.get(j)) - 1 > i) {
  30. continue x;
  31. }
  32. }
  33. }
  34. }
  35. public static void main(String[] args) {
  36. Long temp = System.currentTimeMillis();
  37. // 目前只能算到2^19,之后的效率太低,后期希望加入多线程加快速度以及优化算法
  38. getSushu((long) 600000);
  39. System.out.println("RunTime : " + (System.currentTimeMillis() - temp) / 1000.0 + " s");
  40. }
  41. }

 

运行效果如下