UESTC 2016 Summer Training #2 Div.2 E 分解质因素(除了以后剩下的可能也是个素数)

Source

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=121703#problem/E

My Solution

分解质因数， 至少有三个不同的质因数的数是lucky number, 用修改分解质因数的模版， 是只记录质因数个数就好，不用管是什么而且不同质因数个数大于等于3就return 3

用的分解质因素模版不知道为什么会WA， 改成 2~n, 暴力试除来分解质因数倒是可以⊙﹏⊙‖∣

原因， 对于2~sqrt(n)+1， 可能有剩余的大于 sqrt(n) +1的素数， 也就是还有大于sqrt(n)+1 的质因数， 所以试除全部的2~n比较好

//刚开始做的时候， 看成了，只能有三个不同质数构成的数， 然后就搞出个素数表，然后构造，然后用小根堆保存， 然后从那10000000多个根据要求的数中拿出最小的1000多个放到thisans[]里

//(┬＿┬)成功浪费了一大堆时间

#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn = 20000 + 9;
int ans[maxn];

int factor(int n)
{
    int tot = 0;
    int temp, i, now;
    //temp = (int)((double)sqrt(n) + 1);
    now = n;
    for(int i = 2; i <= n; i++){ //!!!!!!为什么不能用temp呢 if(now%i == 0){ tot++; if(tot >= 3) return tot;
        }
        while(now%i == 0){
            now/=i;
        }
    }
    return tot;
}


int main()
{
    int t = 1, num = 2;
    while(t < 1009){ if(factor(num) >= 3) {ans[t] = num; t++;}
        num++;

    }
    //cout<<factor(4588)<<endl; #ifdef LOCAL freopen("a.txt", "r", stdin); //freopen("b.txt", "w", stdout); #endif // LOCAL LL T, n; cin>>T;
    while(T--){
        cin>>n;
        cout<<ans[n]<<endl;

    }
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx