Gemma ha appena imparato che cos’è un numero semiprimo, e presa dall’euforia non riesce a smettere di parlarne.
In particolare, un numero semiprimo è un intero ≥2 che si fattorizza come prodotto di due numeri primi (non necessariamente distinti).
I numeri primi sono tutti quegli interi ≥2 divisibili solo per se stessi e per 1.
Sono quindi esempi di numeri semiprimi i numeri:
- 15, prodotto di 3 e 5.
- 169, prodotto di 13 e 13.
Aiuta Gemma a scrivere un programma che verifichi se un numero N è semiprimo oppure no!
Dati di input
Il file input.txt contiene l’unico intero N, di cui Gemma vuole verificare la semiprimalità.
Dati di output
Il file output.txt contiene:
- I due primi che fattorizzano N, stampati su un’unica riga, in ordine non-decrescente, se N è semiprimo.
- L’unico intero −1 se N non è semiprimo.
Assunzioni
- 2 ≤ N ≤ 1000000.
Esempi di input/output
| input.txt | output.txt |
| 961 | 31 31 |
| 884053 | 101 8753 |
| 16 | -1 |
Note
- Per chi usa Pascal: è richiesto che si utilizzi sempre il tipo di dato longint al posto di integer.
- Un programma che stampa lo stesso output indipendentemente dal file di input non totalizza alcun punteggio.
/*
www.valcon.it/
OII 2015 - Fase territoriale - NUMERO SEMIPRIMO
*/
#include
#include
long N;
long P, P1, P2;
int primo(long x)
{
long ultimo=(long)sqrt(x);
for(long i=2; i <= ultimo; i++)
if(x%i == 0)
{
P=i;
return 0;
}
return 1;
}
int main()
{
FILE *fin =fopen( "input.txt", "r");
FILE *fout=fopen("output.txt", "w");
fscanf(fin, "%ld", &N);
if(primo(N))
fprintf(fout, "-1\n");
else
{
P1=P;
P2=N/P;
if(primo(P1) && primo(P2))
fprintf(fout, "%ld %ld\n", P1,P2);
else
fprintf(fout, "-1\n");
}
return 0;
}