Prime numbers program

This is a discussion on Prime numbers program within the C Programming forums, part of the General Programming Boards category; The problem statement is the following Problem Statement The first known prime found to exceed one million digits was discovered ...

  1. #1
    Registered User
    Join Date
    Oct 2010
    Posts
    11

    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: 284332^(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 ?

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,484
    > 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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Registered User
    Join Date
    Oct 2010
    Posts
    11
    oh yeah ... thanks for pointing it out

  4. #4
    Registered User
    Join Date
    Oct 2010
    Posts
    107
    Please post it back when you get it to work? It would be interesting to compile myself.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Program Plan
    By Programmer_P in forum C++ Programming
    Replies: 0
    Last Post: 05-11-2009, 01:42 AM
  2. Need a little help with Cyclic Numbers Program
    By SlyMaelstrom in forum C++ Programming
    Replies: 3
    Last Post: 10-19-2005, 05:01 PM
  3. Perfect Numbers C Program
    By SlayerBlade in forum C Programming
    Replies: 2
    Last Post: 08-28-2005, 05:11 PM
  4. Replies: 3
    Last Post: 01-14-2003, 09:34 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21