JAVA实现简单梅森素数算法

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

梅森素数是由梅森数而来。
所谓梅森数,是指形如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之后再算出梅森素数的效率就明显变慢,后来打算用多线程实现也一直就搁置了,以后有机会再研究。

package test;

import java.util.ArrayList;
import java.util.List;

/**
 * bumblebee 2017-09-12
 * 梅森素数公式 : 2^p -1 = Mp		p为素数时 Mp为梅森数			若Mp也为素数时 , 2^p - 1 为梅森素数
 */
public class T2 {
	/**
	 * 传入计算范围最大值LONG l,排除法找出范围内梅森素数并输出
	 */
	public static void getSushu(Long l) {
		List<Long> list = new ArrayList<Long>();
		int c = 1;
		x: for (long i = 2; i < l; i++) {
			for (int j = 0; j < list.size(); j++) {
				// i能被list中的数字整除则跳出循环
				if (i % list.get(j) == 0)
					continue x;
			}
			//不能被比自己小的所有素数整除的数字必是一个素数,装入list
			list.add(i);
			//到这里再继续判断这个素数是否梅森素数 与比自己小的所有的素数过一遍公式,配上就是梅森素数,如果超过i的大小则不用继续
			for (int j = 0; j < list.size(); j++) {
				if (Math.pow(2, list.get(j)) - 1 == i) {
					System.out.println(c++ + "\t2^" + list.get(j) + "-1\t=\t" + i);
				} else if (Math.pow(2, list.get(j)) - 1 > i) {
					continue x;
				}
			}
		}
	}
	public static void main(String[] args) {
		Long temp = System.currentTimeMillis();
		// 目前只能算到2^19,之后的效率太低,后期希望加入多线程加快速度以及优化算法
		getSushu((long) 600000);
		System.out.println("RunTime : " + (System.currentTimeMillis() - temp) / 1000.0 + " s");
	}
}

 运行效果如下

赠人玫瑰 手留余香
查重
CSVUtils.java
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论