1. 
/**
* 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)));
}
}
}