Cod sursa(job #585615)

Utilizator robigiirimias robert robigi Data 30 aprilie 2011 10:19:15
Problema NumMst Scor 9
Compilator cpp Status done
Runda Algoritmiada 2011, Runda Finală, Clasele 10-12 Marime 0.77 kb
#include <cstdio>

using namespace std;

FILE *f=fopen("nummst.in", "r");
FILE *g=fopen("nummst.out", "w");

int n;
bool v[10000001];


int main()
{
    fscanf(f, "%d", &n);

    if (n%2==0)
    {
        fprintf(g, "%d %d", n/2, n/2);

        fclose(f);
        fclose(g);

        return 0;
    }

    int i=0;
    int ok=0;

    for (i=2; i<=n/2; ++i)
    {

        if (v[i]==0)
        {
            if (n%i==0)
             {
                 ok=1;
                 break;
             }
            for (int j=i+i; j<=n/2; j+=i)
                v[j]=1;
        }
    }

    if (ok)
        fprintf(g, "%d %d", n/i, n-n/i);
    else
        fprintf(g, "%d %d", n/2, n/2+1);


    fclose(f);
    fclose(g);

    return 0;
}