分享程序员开发的那些事...
更新时间：2022-10-13 11:56:53
如果一个数字的所有真因子之和等于自身，则称它为“完全数”或“完美数”
例如：
6 = 1 + 2 + 3 28 = 1 + 2 + 4 + 7 + 14
早在公元前 300 多年，欧几里得就给出了判定完全数的定理：
若 2^n - 1 是素数，则 2^(n-1) * (2^n - 1) 是完全数。因为法国数学家梅森的猜想，我们习惯上把形如：2^n - 1 的素数称为：梅森素数。 截止到2021年10月6日，找到了第48个梅森素数。新近找到的梅森素数太大，以至于难于用一般的编程思路窥其全貌，所以我们把任务的难度降低一点：
19631 年，美国伊利诺伊大学为了纪念他们找到的第 23 个梅森素数 n=11213， 在每个寄出的信封上都印上了2^11213−1 是素数”的字样。 2^11213−1 这个数字已经很大(有 3000 多位)，请你编程求出这个素数的十进制表示的最后 100 位。
数组的熟练、进位取余、取模 建议用时15~25min
题目要求求出2^11213−1的最后一百位，普通的int、long long int 可承受不了这么大的数据量，我们换一种思路。
为什么不用数组存储，仅仅一个100位的数组就可以解决问题。数组第一个元素设为1，每一次每个元素乘以一个2，超出则向前进一位，剩下%10为当前位。
928*2，数组存储a[3]=1=8,a[2]=2,a[1]=8。 a[1]*2+0=16，超出向前进位，那a[1]=a[1]%10=6 a[2]*2+1=5,不要进位，加的1是之前8进的 a[3]*2+0=18,超出向前进位，那a[3]=a[3]%10=8 a[4]=1 结果为1856
#include<iostream> using namespace std; int main() { int i,j,n=11213,m,a[108]={0};//初始化定义 a[1]=1;//定义第一项 for(i=0;i<n;i++)//第一层循环，判断几个2相乘 { int r=0;//进位数 for(j=1;j<=100;j++)//100位直接循环 { m=a[j]*2+r;//m暂时存储结果 a[j]=m%10;//取模 r=m/10;//是否进位 } } a[1]-=1;//第一项别忘记-1哦 for(i=100;i>=1;i--)//输出结果 cout<<a[i]; return 0; }
输出结果为：8586718527586602439602335283513944980064327030278104224144971883680541689784796267391476087696392191