1.

/*
* ACM Contest training
* Problem: 11610 - Reverse Prime
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=78&page=show_problem&problem=2657
*
* @author Christoph Goettschkes
* @version 1.0, 01/02/2011
*
* Method : Sieve of eratosthenes, dynamic programming
* Status : Accepted
* Runtime: 0.552
*/

#include <stdio.h>
#include <iostream>
#include <math.h>
#include <vector>
#include <algorithm>

using namespace std;

int sieve[1000005];
vector<int> reversePrimes;
vector<int> factors;
int factorsSum[1000005];

void calcSieve()
{
int upperBound = 1000005;
int upperBoundSquareRoot = (int)sqrt(upperBound);
for (int m = 2; m <= upperBoundSquareRoot; m++) {
if (sieve[m] == 0) {
for (int k = m * m; k <= upperBound; k += m) {
sieve[k] = m;
}
}
}
}

int countPrimeFaktors(int x) {
int counter = 0;
while (x % 2 == 0) {
counter++;
x /= 2;
}

while (x % 3 == 0) {
counter++;
x /= 3;
}

while (x % 5 == 0) {
counter++;
x /= 5;
}

while (sieve[x] != 0) {
counter++;
x /= sieve[x];
}

if (x != 1) {
counter++;
}
return counter;
}

void getFactors() {
int reverseSize = reversePrimes.size();
for (int i = 0; i < reverseSize; i++) {
factors.push_back(countPrimeFaktors(reversePrimes[i]));
}
}

int reverse(int x) {
int tmp = 0;
while (x > 0) {
tmp = tmp * 10 + x % 10;
x /= 10;
}
return tmp;
}

void getReversePrimes() {
for (int i = 1000010; i < 10000000; i += 10) {
int rev = reverse(i);
if (rev < 1000000 && !sieve[rev])
reversePrimes.push_back(i);
}
sort(reversePrimes.begin(), reversePrimes.end());
}

void sum(int startIndex) {
if (startIndex == 0) {
factorsSum[0] = factors[0];
startIndex = 1;
}
int factorsSize = factors.size();
for (int i = startIndex; i < factorsSize; i++) {
factorsSum[i] = factorsSum[i - 1] + factors[i];
}
}

int binSearch(const vector<int> &arr, int key) {

int left = 0, right = arr.size() - 1, mid;

while (left <= right) {
mid = (int) ((left + right) / 2);
if (key == arr[mid])
return mid;
else if (key > arr[mid])
left = mid + 1;
else
right = mid - 1;
}

return -1;
}

void del(int x) {
int key = binSearch(reversePrimes, x);
if (key < 0)
return;

reversePrimes.erase(reversePrimes.begin() + key);
factors.erase(factors.begin() + key);
sum(key);
}

int main()
{
calcSieve();
getReversePrimes();
getFactors();
sum(0);

char s[30];
int x;
while(scanf("%s %d", s, &x) != EOF)
{
if(s[0] == 'q')
cout << factorsSum[x] << endl;
else
del(x);
}
}


2.
/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS2010
* Problem: 11610 - Reverse Prime
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=78&problem=2657&mosmsg=Submission+received+with+ID+7925750
*
* @author Barny Porcio
* @version 1.0, 04/26/2010
*
* Status : Accepted
* Runtime: 0.156
*/
#include <iostream>
#include <set>
#include <math.h>
#include <algorithm>
using namespace std;
set<int> primes;

/**
* Gibt die anzahl der Primfaktoren der Zahl zahl zurück,
* indem die zahl versucht wird durch eine liste mit primfaktoren zu teilen
*/
int anzahlprimfactor(int zahl){
int counter = 0;
set<int>::iterator it = primes.begin();
int teiler = *it;
int sqrtzahl = ((int) sqrt(zahl))+1;
while (zahl != 1){
if (teiler >= sqrtzahl){
++counter;
break;
}
if (zahl % teiler == 0){
zahl /=teiler;
++counter;
sqrtzahl = ((int) sqrt(zahl))+1;
}
else{
teiler = *(++it);
}
}
return counter;
}
int main(){
const int N = 78498;
bool* noprimes = new bool[1000000];
int * inverse = new int[N];
int primcou = 0;

for (int i = 2; i <= 1000;i +=2){
if(noprimes[i] != true){
int remaining = i;
int invert = 0;
while (remaining != 0 ){
invert *= 10;
invert += remaining%10;
remaining = remaining/10;
}
for (int laenge = (int)ceil(log10(invert)); laenge < 7 ;++laenge)
invert *= 10;
inverse[primcou] =invert;
primes.insert(i);
for (int u = 2;u*i<1000000;++u ){
noprimes[u*i] = true;
}
++primcou;

if (i == 2)
--i;
}
}
/**das sieb muss noch durchgegangen werden und alle primzahlen in die primzahlenliste eingetragen werden,
*sowie die Inversen davon in die inverse liste.
*/
for (int i =1001;i< 1000000; i += 2 ){
if(noprimes[i] != true){
int remaining = i;
int invert = 0;
while (remaining != 0 ){
invert *= 10;
invert += remaining%10;
remaining = remaining/10;
}
for (int laenge = (int)ceil(log10(invert)); laenge < 7 ;++laenge)
invert *= 10;
inverse[primcou] =invert;
primes.insert(i);
++primcou;
}
}
delete[] noprimes; //speicher des siebs freigeben, wird nicht mehr benötigt
sort(inverse, inverse+N);


int * commul = new int[N]; //Array in dem die zusammengezählten Werte der anzahl der Primfaktoren aller inverseprimes gespeichert werden
int temp = 0;
for (int z = 0; z < N; ++z){
temp += anzahlprimfactor(inverse[z]);
commul[z] = temp;
}

set<pair<int,int> > deleted; //set in dem alle gelöschten zahlen gespeichert werden, first ist die zahl selbst, secound ist die anzahl der primfaktoren
char c;
int zahl;
while(cin>>c>>zahl){
if (c == 'q'){
int ans = 0 ;
int counter = 0;
/*
* schaut nach was der zusammengezählte Wert von der zahl+k ist, wobei k hier die anzahl der gelöschten zahlen in diesem intervall ist
* von dem Wert wird dann noch die summe der anzahl der primfaktoren der gelöschten abgezogen
*/
for(set<pair<int,int> > ::iterator iteer = deleted.begin(); iteer != deleted.end();++iteer){
if ( (*iteer).first > inverse[zahl+counter])
break;
++counter;
ans -= (*iteer).second;
}
ans += commul[zahl+counter];
cout <<ans <<endl;
}
else if (c == 'd'){
//die zahl wird in der gelöscht liste eingetragen
deleted.insert(pair<int, int >(zahl,anzahlprimfactor(zahl)));
}
}
}