2 solutions

  • 0
    @ 2022-3-11 13:30:34

    思路分析:

    本题是求从1到n中,恰好有2个不同的质因数的数的个数(英文原文是 exactly,刚开始被卡wa就是想当然的当成至少有2个质因数了......英文题读题还是要仔细啊)。找质因数,自然而然的就想到了唯一分解定律,关于唯一分解定律,谢队在蓝桥杯训练真题—完全平方数的题解中讲的很详细和清楚了,有代码和视屏,不清楚的可以乘机去学习下。所以,我的做法就是遍历1-n,找每个数的质因数个数,满足条件就计数器加一,最后输入结果即可,对了,由于找质因数的模板是找到所有的质因数,可能出现多个相同的质因数,而本题是要求不同的质因数个数,所以可以用set来去重。

    参考代码:

    #include <bits/stdc++.h>
    using namespace std;
    set<int> s;
    
    int main() {
        int n, t = 0, ans = 0;
        cin >> n;
        for (int i = 6; i <= n; i++) {
        	s.clear();
        	int temp = i;
            for (int j = 2; j * j <= temp; j++) {// 模板开始
                while (temp % j == 0) {
    				s.insert(j);
                    temp /= j;
                }
            }
            if (temp > 1) s.insert(temp);// end
            t = s.size();
            if (t == 2) ans++;
        }
        cout << ans;
        return 0;
    }
    

    Information

    ID
    1924
    Time
    2000ms
    Memory
    256MiB
    Difficulty
    5
    Tags
    # Submissions
    42
    Accepted
    16
    Uploaded By