Thread: Prime numbers program

The problem statement is the following
Problem Statement

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.

My code is here:

Code:

#include <stdio.h>
int main()
{
    int a[10], i, j;
    for(i=0; i<20; i++)
    {
             a[i] = 0;
             a[9] = 1;
    }
    for(i=1; i <= 7830461; i++)
    {
              for(j = 9; j>=0; j--)
              {
                    a[j] *= 2;
                    
              }
              for(j=9; j>=0; j--)
              {
                    if (a[j] >= 10)
                    {
                             a[j-1]+= a[j]/10;
                             a[j] = a[j]%10;
                    }
              }
              //printf("%d%d%d%d%d%d%d%d%d%d\n", a[0],a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9]);
    }
    printf("%d%d%d%d%d%d%d%d%d%d\n", a[0],a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9]);
    for(j=9; j>=0; j--)
    {
              a[j] *= 28433;
    }
    for(j=9; j>=0; j--)
    {
           if (a[j] >= 10)
           {
                   a[j-1] += a[j]/10;
                   a[j] = a[j]%10;
           }
    }
    a[9]++;
    printf("%d%d%d%d%d%d%d%d%d%d", a[0],a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9]);
    getch();
}

the code gives the wrong result. I was trying to analyze it. When in the first for loop, i put the limit i <= 34 and i <= 35, it gave the same output .. (it worked fine for all i <= 34). then after i = 34, the answers it gave were actually for i-1 i.e. i <= 35 gave answer for i<=34, i <=36 gave answer for i<=35 .. i did not bother to check higher values because i found that the final answer for i <= 7830461 is given much after i = 7830461.

Why is this happening ?

oh yeah ... thanks for pointing it out

Please post it back when you get it to work? It would be interesting to compile myself.