/*
Numere prime
presudocod

citeste n;
prim=1;
pentru k=2 pana la n/2 executa
            daca (rest(n,k)=0) atunci executa
                                                    prim=0;
                                                    k=n;
                                                    sf_executa
daca (prim=1) atunci afiseaza "prim"
                         altfel  afiseaza "nu este prim"

--------------------------------------------------

citeste n;
prim=1;
pentru k=2 pana la radical(n) executa
            daca (rest(n,k)=0) atunci executa
                                                    prim=0;
                                                    k=n;
                                                    sf_executa
daca (prim=1) atunci afiseaza "prim"
                         altfel  afiseaza "nu este prim"



#include<iostream>
#include<math.h>
using namespace std;
int n;
int main()
{
    cout<<"n=";cin>>n;
    int prim,k; prim=1;
    for(k=2;k<=(int)sqrt(n);k++)
            {
                if (n%k==0) {
                                        prim=0;
                                        // k=n;
                                        break;
                                    }
            }
     if (prim==1)         cout<<"Prim !";
            else   cout<<" Nu este !";
}


Fie n numar natural.
Sa se descompuna intr-o suma cu numar minim de termeni numere prime

Conjectura lui Golbarch
Orice numar natural n > 2 poate descompus ca suma de 2 numere prime.

citeste n;
aux=n-2;
gasit=0;
atata timp cat gasit=0 executa
        - daca (aux este numar prim) atunci  executa
                    - daca (n-aux este numar prim)  atunci   executa
                                                                                      gasit=1;
                                                                                     sf_executa
                                                                          altfel aux=aux-1
                                                                   sf_executa
                                                        altfel aux=aux-1
afiseaza aux
afiseaza n-aux
*/

#include<iostream>
#include<math.h>
using namespace std;
int n;
int main()
{
    cout<<"n=";cin>>n;
    int k;
    int aux,gasit;
    aux=n-2;
    gasit=0;
    while(gasit==0) {
                int prim1=1;
                for(k=2;k<=((int)sqrt(aux));k++)
                { if (aux%k==0) { prim1=0;break;} }
                if (prim1==1)     {
                                            int prim2=1;
                                            for(k=2;k<=(int)sqrt(n-aux);k++)
                                             if ((n-aux)%k==0) { prim2=0;break;}
                                             if (prim2==1)     { gasit=1; break;}
                                                              else aux=aux-1;
                                          }
                            else aux=aux-1;
                                }
cout<<endl<<aux;
cout<<endl<<n-aux;
}