蓝桥杯2013试题-java梅森素数

2019-11-08 01:02:51

字体：大中小

来源：转载

供稿：网友

如果一个数字的所有真因子之和等于自身，则称它为“完全数”或“完美数”例如：6 = 1 + 2 + 328 = 1 + 2 + 4 + 7 + 14早在公元前300多年，欧几里得就给出了判定完全数的定理：若 2^n - 1 是素数，则 2^(n-1) * (2^n - 1) 是完全数。其中 ^ 表示“乘方”运算，乘方的优先级比四则运算高，例如：2^3 = 8， 2 * 2^3 = 16, 2^3-1 = 7但人们很快发现，当n很大时，判定一个大数是否为素数到今天也依然是个难题。因为法国数学家梅森的猜想，我们习惯上把形如：2^n - 1 的素数称为：梅森素数。截止2013年2月，一共只找到了48个梅森素数。新近找到的梅森素数太大，以至于难于用一般的编程思路窥其全貌，所以我们把任务的难度降低一点：1963年，美国伊利诺伊大学为了纪念他们找到的第23个梅森素数 n=11213，在每个寄出的信封上都印上了“2^11213-1 是素数”的字样。2^11213 - 1 这个数字已经很大(有3000多位)，请你编程求出这个素数的十进制表示的最后100位。

答案是一个长度为100的数字串，请通过浏览器直接提交该数字。注意：不要提交解答过程，或其它辅助说明类的内容。

方法一import java.math.BigInteger;public void func1() { BigInteger messon = new BigInteger("1"); BigInteger two = new BigInteger("2"); for(int i=0;i<11213;++i) { messon = messon.multiply(two); } String tmp = messon.subtract(BigInteger.ONE).toString(); System.out.PRintln(tmp.substring((tmp.length()-100)));}方法二 public void func2() { int[] pos = new int[100]; pos[0] = 1; int r = 0, j =0; for(int p=0;p<11213;++p) { for(int q=0;q<100;++q) { int tmp = pos[q] * 2;//每一位乘以2 r = tmp%10;//获取余数 pos[q] = r + j;//加上之前的进位 j = tmp/10;//获取进位 } //一遍之后，进位需要清零 j = 0; } for(int q=99;q>0;--q) { System.out.print(pos[q]); } //2的阶乘的位数一定不为0，可放心的减1 System.out.println(pos[0] - 1); }输出Compiling Messon.java.......-----------OUTPUT-----------func18586718527586602439602335283513944980064327030278104224144971883680541689784796267391476087696392191func28586718527586602439602335283513944980064327030278104224144971883680541689784796267391476087696392191[Finished in 3.3s]

下面的两种方法均为Java语言

上一篇：Java注解--Annotation

下一篇：Java对象克隆