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