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 ?