Cod sursa(job #1642947)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 9 martie 2016 16:58:02
Problema Mins Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <cstdio>
#include <vector>
using namespace std;

int n,m;
bool ciur[5005];
vector<int> p;

void erat(int lim){
    ciur[0]=1;
    ciur[1]=1;
    for(int i=4; i<=lim; i+=2)
        ciur[i]=1;
    for(int i=3; i*i<=lim; i+=2){
        if(ciur[i])
            continue;
        for(int j=i*i; j<=lim; j+=i*i)
            ciur[j]=1;
    }
    for(int i=2; i<=lim; ++i)
        if(!ciur[i])
            p.push_back(i);
}

inline int furt(int n){
    int r=0,cn=n;
    bool flag;
    vector<int> d;
    for(int i=0; p[i]*p[i]<=n; ++i){
        flag=false;
        while(!(cn%p[i])){
            cn/=p[i];
            flag=true;
        }
        if(flag)
            d.push_back(p[i]);
    }
    if(cn>1)
        d.push_back(cn);

    for(int i=1; i<m; ++i){
        flag=true;
        for(int &j:d){
            if(!(i%j)){
                flag=false;
                break;
            }
        }
        if(flag)
            ++r;
    }
    return r;
}

int main(void){
    freopen("mins.in","r",stdin);
    freopen("mins.out","w",stdout);
    scanf("%d%d",&m,&n);
    erat(max(n,m));
    int ans=0;
    for(int i=1; i<n; ++i)
        ans+=furt(i);
    printf("%d",ans);
    return 0;
}