Goldbach

Corso Online per Potenziare le Competenze Digitali

La congettura di Goldbach afferma che:

Ogni numero pari è ottenibile come somma di due numeri primi.

Per esempio, 16 è la somma di 11 e 5, mentre 20 è la somma di 17 e 3.

Il vostro compito è quello di scrivere un programma che, letto un numero pari, stampi due numeri primi la cui somma corrisponda al numero letto.

Dati di input

Nella prima ed unica riga del file input.txt è presente il numero N, pari.

Dati di output

Stampare sulla prima riga del file output.txt i due numeri P1 e P2.

Assunzioni

• 4 < N < 1000.

Esempi di input/output

input.txt	output.txt
16	11 5
20	3 17

/*  
 www.valcon.it
 Corso Online per Potenziare le Competenze Digitali
 Goldbach
*/

#include
#include
#include
using namespace std;
 
int primo(int x)
{	
	int ultimo=(int)sqrt(x);
	
	for(int i=2; i <= ultimo; i++)
	    if(x%i == 0)
	        return 0;
	return 1;        
}

int main()
{     
    int N,
        P1,P2;

    ifstream fin ( "input.txt");  
    ofstream fout("output.txt");
   
	fin >> N;    			
	for(P1=2; P1 <= N/2; P1++)
    	if(primo(P1))			
    	{    	
    		P2=N-P1;
    		if(primo(P2))
    		    break;
		}		
	fout << P1 << " " << P2;		    	    
    return 0;
}