Project Euler 97 ：Large non-Mersenne prime 非梅森大素数

时间：2024-11-05 20:02:50

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 26972593−1; it contains exactly 2,098,960 digits. Subsequently other Mersenne primes, of the form 2p−1, have been found which contain more digits.

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

Find the last ten digits of this prime number.

非梅森大素数

1999年人们发现了第一个超过一百万位的素数，这是一个梅森素数，可以表示为26972593−1，包含有2,098,960位数字。在此之后，更多形如2p−1的梅森素数被发现，其位数也越来越多。

然而，在2004年，人们发现了一个巨大的非梅森素数，包含有2,357,207位数字：28433×27830457+1。

找出这个素数的最后十位数字。

解题

感觉很简单。。。

JAVA

package Level3;

import java.io.BufferedReader;

import java.io.FileReader;

import java.io.IOException;

import java.math.BigInteger;

import java.util.ArrayList;

public class PE097{

    public static void run() {

        BigInteger m = new BigInteger("10000000000");

        BigInteger r1 = new BigInteger("28433");

        BigInteger t = new BigInteger("2");

        BigInteger exp = new BigInteger("7830457");

        BigInteger res = t.modPow(exp, m);

        res = r1.multiply(res).add(new BigInteger("1"));

        res = res.mod(m);

        System.out.println(res);

    }

    public static void main(String[] args) throws IOException {

        long t0 = System.currentTimeMillis();

        run();

        long t1 = System.currentTimeMillis();

        long t = t1 - t0;

        System.out.println("running time="+t/1000+"s"+t%1000+"ms");

    }

}

// 8739992577
// running time=0s2ms

 

就这样

或者这样

    public static void run2(){

        long base = 2;

        long mod = 1000000000;

        long exp = 7830457;

        long res = 28433;

        for(long i =1;i<=exp;i++){

            res = (res*2)%mod;

        }

        res +=1;

        res %=mod;

        System.out.println(res);

    }

//    739992577

//    running time=0s163ms

上面mod少个0求的是后9位的数，因为多个0就越界了，少一位手工0到9可以暴力遍历。。。

Python

# coding=gbk

import copy

import time as time

def main():

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

t0 = time.time()

main()

t1 = time.time()

print "running time=",(t1-t0),"s"

#

# running time= 0.0190000534058 s

也就这样

相关文章