アルゴ式(beta版)の「整数論的アルゴリズム (beta)」素数と素数判定法からの出典です。
algo-method.com
アルゴ式とは...
>・プログラミングや情報科学をコツコツ学べる「教科書」
>・学んだ内容をゲーム感覚で大量に実践できる「練習問題」
>の2つで構成される、Web上で完結した学習コンテンツです。
・素数と素数判定法
・Q1. 53 の次の素数は?
algo-method.com
/* C++による「整数論的アルゴリズム (beta)」素数と素数判定法の解答例 Q1. 53 の次の素数は? https://algo-method.com/tasks/321 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; int main(void){ for(int i=54; ;i++){ if(i%2==0){ continue; } bool tf=true; for(int j=3;j<=sqrt(i);j+=2){ if(i%j==0){ tf=false; } } if(tf==true){ cout<<i<<endl; return 0; } } }
・Q2. 素数判定 (弱)
algo-method.com
/* C++による「整数論的アルゴリズム (beta)」素数と素数判定法の解答例 Q2. 素数判定 (弱) https://algo-method.com/tasks/318 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; int main(void){ int n; cin>>n; if(n==1 || (n!=2 && n%2==0)){ cout<<"No"<<endl; return 0; } for(int i=3;i<=sqrt(n);i++){ if(n%i==0){ cout<<"No"<<endl; return 0; } } cout<<"Yes"<<endl; }
・Q3. 素数判定 (強)
algo-method.com
/* C++による「整数論的アルゴリズム (beta)」素数と素数判定法の解答例 Q3. 素数判定 (強) https://algo-method.com/tasks/319 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; int main(void){ ll n; cin>>n; if(n==1 || (n!=2 && n%2==0)){ cout<<"No"<<endl; return 0; } for(ll i=3;i<=sqrt(n);i++){ if(n%i==0){ cout<<"No"<<endl; return 0; } } cout<<"Yes"<<endl; }
・Q4. N 以下の最大の素数
algo-method.com
/* C++による「整数論的アルゴリズム (beta)」素数と素数判定法の解答例 Q4. N 以下の最大の素数 https://algo-method.com/tasks/320 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; int main(void){ ll n; cin>>n; for(int i=n;i>1;i--){ if(i!=2 && i%2==0){ continue; } bool tf=true; for(ll j=3;j<=sqrt(n);j++){ if(i%j==0){ tf=false; } } if(tf==true){ cout<<i<<endl; return 0; } } }
・Q5. ゴールドバッハ予想 (1)
algo-method.com
/* C++による「整数論的アルゴリズム (beta)」素数と素数判定法の解答例 Q5. ゴールドバッハ予想 (1) https://algo-method.com/tasks/322 提出コードの解答例 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>> v1,v2; vector<ll> vi; for(ll i=2;i<n;i++){ if(prime(i)==true){ if(prime(n-i)==true){ v1.push_back({n-i,i}); v2.push_back({i,n-i}); } } } sort(v1.begin(),v1.end()); sort(v2.begin(),v2.end()); cout<<min(v1[0].first,v2[0].first)<<endl; return 0; }
設問の出典は、情報科学をコツコツ積み立てて学習できるサービス「アルゴ式(beta版)」です。
algo-method.com