Untitled

 avatar
unknown
plain_text
a year ago
822 B
0
Indexable
/*
    B(x) = x
    C(a) + C(b) = C(ab)
    D(x) = C(x!)
    x! = p1^a1*p2^a2*p3^a3....
    https://cs.stackexchange.com/questions/138689/four-functions-problem
*/
int largestPower(int n, int p){
    int x = 0;
    while(n){
        n/=p;
        x+=n;
    }
    return x;
}
int main()
{
    int n;
    cin>>n;
    vector<int> primes;
    bool arr[n+1];
    memset(arr, true, sizeof(arr));
    for(int p=2;p*p<=n;p++){
        if(arr[p] == true){
            for(int i=p*p;i<=n;i+=p){
                arr[i] = false;
            }
        }
    }
    for(int i=2;i<n;i++){
        if(arr[i]){
            primes.push_back(i);
        }
    }
    int ans = 0;
    for(int i=0;i<primes.size();i++){
        ans+=(largestPower(n, primes[i]));
    }
    cout<<ans<<endl;
    return 0;
}