题目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

一行代码：

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

永恒的蓝色梦想

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

debuggerzh

8739992577

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

#include<iostream>
using namespace std;
typedef long long ll;
const ll M = 1e10;
const ll UB = 1e4;

ll fast_power(ll base,ll pow){
  ll res = 1;
  while(pow > 0){
    if (base < UB){
      if (pow & 1)  res = res * base % M;
      base = base * base % M;
      pow >>= 1;
    }
    else{
      res = res * base % M;
      pow -= 1;
    }
  }
  return res;
}

int main(){
  ll c1 = 28433,c2 = 7830457;

  cout << (c1 * fast_power(2,c2) + 1) % M << endl;
  return 0;
}

hveagle

暴力求解即可：

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

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

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