Cod sursa(job #109363)

Utilizator the_dragon_of_rockTzogorean Alex the_dragon_of_rock Data 25 noiembrie 2007 10:29:31
Problema Pairs Scor 0
Compilator cpp Status done
Runda preONI 2008, Runda 1, Clasa a 10-a Marime 1.21 kb
#include<fstream.h>
int n,a[100000],prim[79000],nrp;

void eratostene()
{
    int i,j;
    nrp=0;
    char erat[1000000];
    for (i=1;i<1000000;i++)
        erat[i]=0;
    erat[1]=1;
    for (i=2;i<1000000;i++)
        if (erat[i]==0)
                {
                    prim[++nrp]=i;
                    j=2*i;
                    for (;j<1000000;j+=i)
                        erat[j]=1;
                }    
}    

void citire()
{
    ifstream in("pairs.in");
    in>>n;
    int i;
    for (i=1;i<=n;i++)
        in>>a[i];
    in.close();
}    

void perechi()
{
    int i,j,k,ok,p=0;
    for (i=1;i<n;i++)
        for (j=i+1;j<=n;j++)
                {
                    k=1;
                    ok=0;
                    while(prim[k]<=a[i] && prim[k]<=a[j] && !ok)
                         if (a[i]%prim[k]==0 && a[j]%prim[k]==0)
                                  ok=1;
                         else
                                  k++; 
                   if (!ok)
                         p++;
                }
    ofstream out("pairs.out"); 
    out<<p;   
    out.close();
}    

int main()
{
    eratostene();
    citire();
    perechi();
    
    return 0;
}