ABC215 D – Coprime 2

2023.3.19 AM 10:00 by CBJ

數學

//C++ language

#include<iostream>
#include<vector>
#include<numeric>
using namespace std;
vector<int> f(int x){
    vector<int>ret;
    for(int i=2;i*i<=x;i++){
        while(x%i==0){
            x/=i;
            ret.push_back(i);
        }
    }
    if(x!=1) ret.push_back(x);
    return ret;
}
int main(){
    int n,m; cin>>n>>m;
    vector<int>a;
    vector<int>b(m+1,1);
    b[0]=0;
    for(int i=0;i<n;i++){
        int x; cin>>x;
        a.push_back(x);
    }
    for(int i:a){
        vector<int>v = f(i);
        for(int k:v){
            if(k>m) break;
            if(b[k]){
                for(int j=1;j*k<=m;j++){
                    b[j*k]=0;
                }
            }
        }
    }
    cout<<accumulate(b.begin(),b.end(),0)<<"\n";
    for(int i=1;i<=m;i++) if(b[i]) cout<<i<<"\n";
    return 0;
}

相關文章

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *