题目97：找出非梅森素数28433 × 2^7830457 + 1的最后十位

欧拉计划

Large non-Mersenne prime

The first known prime found to exceed one million digits was discovered in 1999, and is a Mersenne prime of the form ; it contains exactly 2,098,960 digits. Subsequently other Mersenne primes, of the form , have been found which contain more digits.

However, in 2004 there was found a massive non-Mersenne prime which contains 2,357,207 digits: .

Find the last ten digits of this prime number.

题目：

第一个超过一百万位的素数是在 1999 年发现的，并且是一个梅森素数： ；它包含 2,098,960 位。之后包含更多位的，形如 的梅森素数被陆续发现。

但是在 2004 年人们发现了一个巨大的包含 2,357,207 位的非梅森素数： 。

找出这个素数的随后十位。

jerryxjr1220

一行代码：

1. print(28433*pow(2, 7830457, 10**10) +1)%10**10

复制代码

永恒的蓝色梦想

1. print((28433 * pow(2, 7830457, 10000000000) + 1) % 10000000000)

复制代码

debuggerzh

8739992577

Process returned 0 (0x0)   execution time : 0.085 s
Press any key to continue.
防溢出的快速幂

1. #include<iostream>
   
2. using namespace std;
   
3. typedef long long ll;
   
4. const ll M = 1e10;
   
5. const ll UB = 1e4;
   
6. 
   
7. ll fast_power(ll base,ll pow){
   
8.   ll res = 1;
   
9.   while(pow > 0){
   
10.     if (base < UB){
    
11.       if (pow & 1)  res = res * base % M;
    
12.       base = base * base % M;
    
13.       pow >>= 1;
    
14.     }
    
15.     else{
    
16.       res = res * base % M;
    
17.       pow -= 1;
    
18.     }
    
19.   }
    
20.   return res;
    
21. }
    
22. 
    
23. int main(){
    
24.   ll c1 = 28433,c2 = 7830457;
    
25. 
    
26.   cout << (c1 * fast_power(2,c2) + 1) % M << endl;
    
27.   return 0;
    
28. }
    

复制代码

hveagle

暴力求解即可：

1. print(28433*pow(2, 7830457)+1 % 10000000000)

复制代码

由于位数限制，调整至2357207位即可：

1. from sys import *
   
2. set_int_max_str_digits(2357207)
   
3. print(28433*pow(2, 7830457)+1 % 10000000000)

复制代码