Numeri superprimi

Correttore online – Intermedi

Un numero primo è un numero intero x > 1 che ha solo due divisori: 1 e x.
Supponiamo di disporre tutti i numeri primi in ordine crescente e denotiamo con p_i l’elemento i-esimo.
Per esempio si avrà p₁=2, p₂=3, p₃=5, p₅₂=239.

Un numero primo p_i di questa lista crescente si dice superprimo se il suo indice i è primo.
Per esempio, p₂=3, p₃=5 e p₅=11 sono superprimi.

Dovete scrivere un programma che, assegnato un intero k stampi il k-esimo numero superprimo.

Dati di input

Il file di input contiene il numero intero k.

Dati di output

Il file di output deve contenere la soluzione (il k-esimo numero superprimo).

Esempi di input/output

input.txt	output.txt
1	3
2	5

Autore/i

A.S. Stankevich, ACM ICPC Team, St. Petersburg State University of Information Technology, Mechanics and Optic

/*
    www.valcon.it
    Correttore online - Esercizi intermedi - Numeri superprimi
*/

#include
#include
#include

using namespace std;

vector v;

void carica_primi(long numero)
{
	long candidato=v[v.size()-1]+2;		// il prossimo primo potrebbe essere...
	while(v.size() < numero)            // allunga v fino a "numero"
	{		
		long p=1;									// se supera tutti i test
		while(p < v.size() && candidato%v[p] != 0)
			p++;
		if(p >= v.size())                           // se è primo lo aggiungo a v
			v.push_back(candidato);
		candidato += 2;                             // il prossimo candidato è...
	}
}


int main()
{
	ifstream fin ( "input.txt");
	ofstream fout("output.txt");
	
	long k;
	fin >> k;
	
	v.push_back(2);			 // 2 è primo
	v.push_back(3);          // 3 è primo
		
	carica_primi(k);         // riempi v fino a k primi
	long kk=v[k-1];          // k-esimo primo	
	carica_primi(kk);		 // riempi v fino a kk primi

	fout << v[kk-1];         // l'ultimo primo in v
}