# My Weblog

## Project Euler Problem 204

Project euler problem 204 solution is almost similar to Problem 293. I was going through the forum of project euler problem 293 where somebody mentioned this problem. Nothing fascinating except a bit of dynamic programming. c++ code.

```#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include<gmpxx.h>
typedef mpz_class _int;
using namespace std;
vector<_int> V[30],P;

void isprime()
{
bool b[100];
memset(b,0,sizeof b);
for(int i=2;i*i<100;i++) if(!b[i]) for(int j=i*i;j<100;j+=i)b[j]=1;
for(int i=2;i<100;i++) if(!b[i])P.push_back(i);
//for(int i=0;i<P.size();i++) cout<<P[i]<<" ";cout<<endl;
//cout<<P.size();cout<<endl;

}

int main()
{
isprime();
int n=P.size();
_int Lim=1;
for(int i=1;i<=9;i++) Lim*=10;

_int ret=1;
V[0].push_back(1);
while(1) { ret=ret*P[0]; if(ret>Lim) break; V[0].push_back(ret);}
sort(V[0].begin(),V[0].end());
_int tmp,sum=0;
sum+=V[0].size();
for(int i=1;i<P.size();i++)
{
ret=1;
while(1)
{
ret=ret*P[i];
if(ret>Lim) break;
for(int j=0;j<i;j++) //calculate from 0 to previous
{
for(int k=0;k<V[j].size();k++)
{
tmp=ret*V[j][k];
if(tmp>Lim) break;
V[i].push_back(tmp);
}
}

}
sort(V[i].begin(),V[i].end());
sum+=V[i].size();
}

cout<<sum<<endl;
}
```

Compile as
g++ proj_204.cpp -lgmpxx -lgmp