T4题解

T4 6题里最难的（个人向）

#include <iostream>


using namespace std;

int ct(int n) {
    bool isPrime[n+1];//建立一个质数数组
    for (int i=0;i<n+1;i++){
        isPrime[i]=true;
    }
    isPrime[0]=isPrime[1]=false;
    for (int i=2;i*i<=n;++i) {
        if (isPrime[i]){
            for (int j=i*i;j<=n;j+=i) {
                isPrime[j]=false;
            }
        }
    }

    int count=0;
    for (int i=2;i<= n;i++) {
        if (isPrime[i] && n%i==0) {
            count++;
            while (n%i==0) {
                n/=i;
            }
        }
    }
    return count;
}

int main() {

    int n;
    cin>>n;
    cout<<ct(n);

    return 0;
}