寝癖頭の解法

小学生の目線から、勉強中の覚え書きを投稿、更新していきます。

アルゴ式(beta版): C++による「整数論的アルゴリズム (beta)」エラトステネスの篩 (1)の解答例

アルゴ式(beta版)の「整数論アルゴリズム (beta)」エラトステネスの篩 (1)からの出典です。
algo-method.com
アルゴ式とは...
>・プログラミングや情報科学をコツコツ学べる「教科書」
>・学んだ内容をゲーム感覚で大量に実践できる「練習問題」
>の2つで構成される、Web上で完結した学習コンテンツです。

C++による「整数論アルゴリズム (beta)」エラトステネスの篩 (1)の解答例

僕が作成、提出したコードは、以下のとおりです。

・エラトステネスの篩 (1)

・Q1. 30 までの整数への篩
algo-method.com

/*
C++による「整数論的アルゴリズム (beta)」エラトステネスの篩 (1)の解答例
Q1. 30 までの整数への篩
https://algo-method.com/tasks/327
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
bool tf(int n){
    bool r=false;
    for(int i=2;i<=n/2;i++){
        if(n%i==0){
            r=true;
            break;
        }
    }
    return r;
}
int main(void){
    vector<int> v;
    for(int i=1;i<=30;i++){
        v.push_back(i);
    }
    for(int i=0;i<30;i++){
        if(v[i]!=2 && v[i]%2==0){
            v[i]+=100;
        }
        if(v[i]!=3 && v[i]%3==0){
            v[i]+=100;
        }
    }
    for(int i=0;i<v.size();i++){
        if(v[i]<100){
            if(tf(v[i])){
                cout<<v[i]<<endl;
                return 0;
            }
        }
    }
}

・Q2. 100 までの整数への篩
algo-method.com

/*
C++による「整数論的アルゴリズム (beta)」エラトステネスの篩 (1)の解答例
Q2. 100 までの整数への篩
https://algo-method.com/tasks/328
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
bool tf(int n){
    bool r=false;
    for(int i=2;i<=n/2;i++){
        if(n%i==0){
            r=true;
            break;
        }
    }
    return r;
}
int main(void){
    vector<int> v;
    for(int i=1;i<=100;i++){
        v.push_back(i);
    }
    for(int i=0;i<100;i++){
        if(v[i]!=2 && v[i]%2==0){
            v[i]=0;
        }
        if(v[i]!=3 && v[i]%3==0){
            v[i]=0;
        }
        if(v[i]!=5 && v[i]%5==0){
            v[i]=0;
        }
    }
    int cnt=0;
    for(int i=0;i<v.size();i++){
        if(v[i]!=0){
            if(tf(v[i])){
                cnt++;
            }
        }
    }
    cout<<cnt<<endl;
    return 0;
}

・Q3. N 以下の素数の個数
algo-method.com

/*
C++による「整数論的アルゴリズム (beta)」エラトステネスの篩 (1)の解答例
Q3. N 以下の素数の個数
https://algo-method.com/tasks/330
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
int main(void){
    int n;
    cin>>n;
    vector<bool> is_prime;
    is_prime.resize(n+1,true);
    is_prime[0]=false;
    is_prime[1]=false;
    for(int i=2;i<=n;i++){
        if(is_prime[i]==true){
            for(int j=2;i*j<=n;j++){
                is_prime[i*j]=false;
            }
        }
    }
    int cnt=0;
    for(int i=0;i<n+1;i++){
        if(is_prime[i]==true){
            cnt++;
        }
    }
    cout<<cnt<<endl;
    return 0;
}

・Q4. 双子素数
algo-method.com

/*
C++による「整数論的アルゴリズム (beta)」エラトステネスの篩 (1)の解答例
Q4. 双子素数
https://algo-method.com/tasks/357
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
int main(void){
    int n;
    cin>>n;
    vector<bool> is_prime;
    is_prime.resize(n+1,true);
    is_prime[0]=false;
    is_prime[1]=false;
    for(int i=2;i<=n;i++){
        if(is_prime[i]==true){
            for(int j=2;i*j<=n;j++){
                is_prime[i*j]=false;
            }
        }
    }
    int cnt=0;
    for(int i=0;i<=n;i++){
        if(i+2<=n && (is_prime[i] && is_prime[i+2])){
            cnt++;
        }
    }
    cout<<cnt<<endl;
    return 0;
}

・Q5. ゴールドバッハ予想 (2)
algo-method.com

/*
C++による「整数論的アルゴリズム (beta)」エラトステネスの篩 (1)の解答例
Q5. ゴールドバッハ予想 (2)
https://algo-method.com/tasks/331
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
bool prime(ll n){
    if(n==1){
        return false;
    }
    for(ll i=2;i<=sqrt(n);i++){
        if(n%i==0){
            return false;
        }
    }
    return true;
}
int main(void){
    ll n;
    cin>>n;
    vector<pair<ll,ll>> v;
    vector<ll> vi;
    for(ll i=2;i<n;i++){
        if(prime(i)==true){
            if(prime(n-i)==true){
                v.push_back({n-i,i});
            }
        }
    }
    int ans=v.size()-0;
    if(ans%2==0){
        cout<<ans/2<<endl;
    }else{
        cout<<ans/2+1<<endl;
    }
    return 0;
}

・Q6. エラトステネスの区間
algo-method.com

/*
C++による「整数論的アルゴリズム (beta)」エラトステネスの篩 (1)の解答例
Q6. エラトステネスの区間篩
https://algo-method.com/tasks/332
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(void){
    ll a,b;
    cin>>a>>b;
    vector<bool> p1(2000000,true);
    vector<bool> p2(b-a+1,true);
    for(ll i=2;i<=sqrt(b);i++){
        if(p1[i]==false){
            continue;
        }
        for(ll j=i*2;j<=sqrt(b);j+=i){
            p1[j]=false;
        }
        ll n=(a+i-1)/i*i;
        if(n==i){
            n=i*2;
        }
        for(ll j=n;j<=b;j+=i){
            p2[j-a]=false;
        }
    }
    int cnt=0;
    for(ll i=a;i<=b;i++){
        if(p2[i-a]){
            cnt++;
        }
    }
    cout<<cnt<<endl;
    return 0;
}

設問の出典は、情報科学をコツコツ積み立てて学習できるサービス「アルゴ式(beta版)」です。
algo-method.com