Cod sursa(job #2099441)

Utilizator bori2000Fazakas Borbala bori2000 Data 4 ianuarie 2018 13:42:18
Problema Fractii Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <iostream>
#include <fstream>
#include <cmath>

using namespace std;

void feltolt(bool a[], int hossz)
{
    for(int i=1; i<=hossz; i++) a[i]=1;
}

void nullaz(bool a[], int k, int n, int &db)
{
    for(int i=k; i<n; i+=k)
    {
        if(a[i])
        {
            a[i]=0;
            db--;
        }
    }
}

int main()
{
    ifstream f("fractii.in");
    ofstream g("fractii.out");
    int n;
    f>>n;
    int s=1;

    bool szita[1000001];
    int db;
    for(int i=2; i<=n; i++)
    {
        db=i-1;
        feltolt(szita, i);
        for(int j=2; j<=i/2; j++)
        {
            if(szita[j] and i%j==0) nullaz(szita, j, i, db);
        }
        /*cout<<i<<"-re a szita: ";
        for(int j=1; j<=i; j++) cout<<szita[j]<<" ";
        cout<<"db="<<db<<endl;*/
        s+=2*db;
    }
    g<<s<<endl;
    return 0;
}