【唯一分解定理】Sphenic numbers Gym - 101243G

Bertha 。 2022-06-09 02:09 178阅读 0赞

Think:  
1知识点：埃氏筛法+分解质因数  
2题意：输入n(30≤n≤10467397)，判断n是否可以分解为3个不同的质因数，若可以则输出YES，反之输出NO；  
3分析：通过埃式筛法预处理素数，一直筛选到2001000(此时已经筛选出大于2000000的素数)，若n可以分解为3个素数则说明第三个素数必定小于等于n/2/3(由n的数据范围可判断得到第三个素数不会超过2000000)，预处理得到素数表之后将n质因数分解进行判断即可

[vjudge题目链接][vjudge]

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    int p, primes[2001400], a[2001400];
    
    void get_primes();
    
    int main(){
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
        get_primes();
        int n, cnt;
        while(~scanf("%d", &n)){
            cnt = 0;
            for(int i = 0; i < p; i++){
                if(n%primes[i] == 0){
                    cnt++;
                    while(n%primes[i] == 0){
                        n /= primes[i];
                        if(n%primes[i] == 0){
                            cnt = -1;
                            break;
                        }
                    }
                    if(cnt == -1 || cnt > 3)
                        break;
                }
            }
            if(cnt == 3)
                printf("YES\n");
            else
                printf("NO\n");
        }
        return 0;
    }
    void get_primes(){
        p = 0;
        a[1] = 1, a[2] = 0;
        memset(a, 0, sizeof(a));
        for(int i = 2; i <= 2001000; i++){
            if(!a[i]){
                primes[p++] = i;
                for(int j = i*2; j <= 2001000; j += i){
                    a[j] = 1;
                }
            }
        }
    }

[vjudge]: https://vjudge.net/problem/Gym-101243G