PROJECT EULER SOLUTION # 97

Solution to problem number 97 of Project Euler.

Question # 97

The first known prime found to exceed one million digits was discovered in 1999, and is a Mersenne prime of the form 2^69725931; it contains exactly 2,098,960 digits. Subsequently other Mersenne primes, of the form 2^p1, have been found which contain more digits.
However, in 2004 there was found a massive non-Mersenne prime which contains 2,357,207 digits: 284332^7830457+1.
Find the last ten digits of this prime number.

Solution # 97

/**********************************************************************************/

#include<stdio.h>

#include<time.h>

#include<stdlib.h>

int tmp[10];

int arr[10];

void fun();

void add();

int main()

{

       int i;

       long j;

       for(i=0;i<10;i++)

              tmp[i]=arr[i]=0;

       arr[9]=1;

       /*the following loop computes last 10 digits of

              2^7830457 */

       for(j=0;j<7830457;j++)

              fun();

      

       for(i=0;i<28433;i++)

              add();

       tmp[9]+=1;

       for(i=0;i<10;i++)

              printf("%d",tmp[i]);

       printf("\nEXECUTION TIME = %f",clock()/(float)CLK_TCK);

      

       system("pause");

}

void fun()

{

       int i;

       for(i=9;i>=0;i--)

       {

              arr[i]*=2;

             

       }

       for(i=9;i>=0;i--)

       {

              if(arr[i]>9)

              {

                     if(i!=0)

                     {

                           arr[i-1]+=1;

                           arr[i]%=10;

                     }

                     if(i==0)

                           arr[i]%=10;

              }

       }

}

void add()

{

       int i;

       for(i=9;i>=0;i--)

       {

              tmp[i]+=arr[i];

       }

       for(i=9;i>=0;i--)

       {

              if(tmp[i]>9)

              {

                     if(i!=0)

                     {

                           tmp[i-1]+=1;

                           tmp[i]%=10;

                     }

                     if(i==0)

                           tmp[i]%=10;

              }

       }

}

/**********************************************************************************/