PROJECT EULER SOLUTION # 29

Solution to problem number 29 of Project Euler
Question # 29
Consider all integer combinations of a^b for 2 a 5 and 2 b 5:

2²=4, 2³=8, 2⁴=16, 2⁵=32
3²=9, 3³=27, 3⁴=81, 3⁵=243
4²=16, 4³=64, 4⁴=256, 4⁵=1024
5²=25, 5³=125, 5⁴=625, 5⁵=3125

If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

How many distinct terms are in the sequence generated by a^b for 2 a 100 and 2 b 100?

Solution # 29

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

#include<stdio.h>

#include<math.h>

int a,b;

struct pair

{

      int x,y;

};

struct pair p[9801];

int isEqual(int,int);

void setToBasic(int);

int main()

{

      int i,j,counter=0,answer;

      for(i=2;i<=100;i++)

            for(j=2;j<=100;j++)

            {

                  p[counter].x=i;

                  p[counter].y=j;

                  counter++;

            }

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

            setToBasic(i);

      answer=9801;

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

            for(j=i-1;j>=0;j--)

                  if(p[i].x && p[i].y && isEqual(i,j))

                        answer--;

      printf("answer = %d\n",answer);

      return 0;

}

int isEqual(int i,int j)

{

      if(p[i].x==p[j].x && p[i].y==p[j].y)

      {

            p[j].x=p[j].y=0;

            return 1;

      }

      return 0;

}

void setToBasic(int counter)

{

      int i,j;

      for(i=2;i<p[counter].x;i++)

            for(j=2;pow(i,j)<=p[counter].x;j++)

                  if(pow(i,j)==p[counter].x)

                  {

                        p[counter].x=i;

                        p[counter].y*=j;

                  }

}

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