一道Java编程题如果一个数字的所有真因子之和等于自身,则称它为“完全数”或“完美数”例如：6=1+2+328=1+2+4+7+14早在公元前300多年,欧几里得就给出了判定完全数的定理：若2^n-

Question

一道Java编程题
如果一个数字的所有真因子之和等于自身,则称它为“完全数”或“完美数”
例如：6 = 1 + 2 + 3
28 = 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位.

Answer 1

class  WangTi2
{
public static void main(String[] args) 
{   
long start = System.currentTimeMillis();//看一下要运行多长时间
shuanShu();
long end = System.currentTimeMillis();//看一下要运行多长时间
System.out.println("用时"+(end-start));

}

public static void shuanShu()
{
int[] arr = new int[100];
arr[0] = 1;
for(int x=0;x<11213;x++)  //可以把11213改成100验证方法的正确性
{  //2^20=1048576 
int z = 0; 
/*
这个循环是记录乘2的结果
*/
for(int y =0;y{

arr[y] = arr[y]<<1;
arr[y] = arr[y] + z;
if (arr[y]>9)
{
arr[y] -= 10;
if(y!=arr.length-1)
z = 1;
}
else z = 0;
}
}
arr[0]--; //这个给最后一个位减1,这个值不会是负数.
System.out.println("这个数的最后100位是：");
for(int x=arr.length-1;x>=0;x--)
{
System.out.print(arr[x]);
if(x%3==0&&x!=0)
System.out.print(",");
}
System.out.println();
}
}

思路是有的.定义数组,只存储最后100位.然后不停的乘2,大于9的向上一个数组加1.重复11213次.再把第一个数组减1.这样做是可以的.效率很低.求高人解答.呵呵.