Saturday 2 November 2013

PROJECT EULER SOLUTION # 29


Solution to problem number 29 of Project Euler
Question # 29
Consider all integer combinations of ab for 2 ≤a ≤5 and 2 ≤b ≤5:
22=4, 23=8, 24=16, 25=32
32=9, 33=27, 34=81, 35=243
42=16, 43=64, 44=256, 45=1024
52=25, 53=125, 54=625, 55=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 ab 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;
                  }
}
/****************************************************************/

No comments:

Post a Comment