欧拉计划 发表于 2016-8-12 01:03:48

题目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 发表于 2016-10-20 13:41:41

一行代码：
print(28433*pow(2, 7830457, 10**10) +1)%10**10

永恒的蓝色梦想 发表于 2019-8-4 10:45:06

本帖最后由 永恒的蓝色梦想 于 2020-8-10 11:15 编辑

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

debuggerzh 发表于 2020-8-20 09:52:57

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 发表于 2024-5-19 20:32:25

本帖最后由 hveagle 于 2024-5-19 20:35 编辑

暴力求解即可：
print(28433*pow(2, 7830457)+1 % 10000000000)
由于位数限制，调整至2357207位即可：
from sys import *
set_int_max_str_digits(2357207)
print(28433*pow(2, 7830457)+1 % 10000000000)
页: [1]
查看完整版本: 题目97：找出非梅森素数28433 × 2^7830457 + 1的最后十位