Project Euler Problem #97!

October 15th, 2009
by Serinox

This solution is brought to you by a lot of boredom in class.

Problem #97 says:

The first known prime found to exceed one million digits was discovered in 1999, and is a Mersenne prime of the form 2^(6972593)−1; it contains exactly 2,098,960 digits. Subsequently other Mersenne primes, of the form 2^(p)−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×2^(7830457)+1.

Find the last ten digits of this prime number.

This is actually quite simple to solve once you realize that you only need to keep track of the last 10 digits. the rest are throw aways. Solution provided in c#/mono runs in about 12 seconds. I feel that I should point out that you can also go to wolfram-alpha and get the answer from typing in the exponent and reading the last 10 digits it provides you with on the page. from there you can multiply by 28433 and add one. So anyways heres the solution:

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace ProjectEuler
{
    class Program
    {
        static void Main(string[] args)
        {
            Stopwatch sw = new Stopwatch();
            sw.Start();
            int Count = 1;
            long Start = (long)Math.Pow(2,100);
            Start = 2;
            while (Count < 7830457)
            {
                if (Count % 500000 == 0)
                    Console.WriteLine(Count);
                Start = Start * 2;
                if (Start.ToString().Length >= 10)
                    Start = long.Parse(Start.ToString().Substring(Start.ToString().Length - 10));
                Count++;
            }
            Start = Start * 28433 + 1;
            Start = long.Parse(Start.ToString().Remove(0, Start.ToString().Length - 10));
            Console.WriteLine(sw.Elapsed);
            Console.WriteLine(Start);
            Console.ReadLine();
        }
    }
}

Posted in Project Euler | Comments (0)

No comments yet

Leave a Reply

You must be logged in to post a comment.