# Prime numbers program

• 10-16-2010
Prestige
Prime numbers program
The problem statement is the following
Problem Statement
Quote:

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 ?
• 10-16-2010
Salem
> for(i=0; i<20; i++)
you've just trashed your array of 10 elements.

> a[j-1]+= a[j]/10;
If j is 0, you've just stepped off the other end as well.
• 10-16-2010
Prestige
oh yeah ... thanks for pointing it out
• 10-16-2010