paizaラーニングのレベルアップ問題集「素数メニュー」からの出典です。
paiza.jp
C++による「素数メニュー」問題集: 最小公倍数と、それらの提出コードの解答例です。
僕が作成、提出したコードは、以下のとおりです。
・STEP: 1 素因数分解
/* C++による「素数メニュー」問題集: 最小公倍数 STEP: 1 素因数分解 https://paiza.jp/works/mondai 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; vector<pair<int,int>> f(int n){ vector<pair<int,int>> v; for(int i=2;i<=sqrt(n);i++){ if(n%i!=0){ continue; }else{ int cnt=0; while(n%i==0){ cnt++; n/=i; } v.push_back(pair(i,cnt)); } } if(n!=1){ v.push_back(pair(n,1)); } return v; } int main(void){ int n; cin>>n; vector<pair<int,int>> ans=f(n); for(auto a:ans){ for(int i=0;i<a.second;i++){ cout<<a.first<<endl; } } return 0; }
・STEP: 2 約数の個数
/* C++による「素数メニュー」問題集: 最小公倍数 STEP: 2 約数の個数 https://paiza.jp/works/mondai 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; vector<pair<int,int>> f(int n){ vector<pair<int,int>> v; for(int i=2;i<=sqrt(n);i++){ if(n%i!=0){ continue; }else{ int cnt=0; while(n%i==0){ cnt++; n/=i; } v.push_back(pair(i,cnt)); } } if(n!=1){ v.push_back(pair(n,1)); } return v; } int main(void){ int n; cin>>n; vector<pair<int,int>> vp=f(n); int ans=1; for(auto a:vp){ ans*=(a.second+1); } cout<<ans<<endl; return 0; }
・STEP: 3 最大公約数
/* C++による「素数メニュー」問題集: 最小公倍数 STEP: 3 最大公約数 https://paiza.jp/works/mondai 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; int gcd(int a,int b){ int i; while(b>0){ i=a%b; a=b; b=i; } return a; } int main(void){ int n; cin>>n; vector<int> a(n); cin>>a[0]; int ans=a[0]; for(int i=1;i<n;i++){ cin>>a[i]; ans=gcd(ans,a[i]); } cout<<ans<<endl; return 0; }
・FINAL問題: 最小公倍数
/* C++による「素数メニュー」問題集: 最小公倍数 FINAL問題: 最小公倍数 https://paiza.jp/works/mondai 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; ll gcd(ll a,ll b){ ll i; while(b>0){ i=a%b; a=b; b=i; } return a; } ll lcm(ll a,ll b){ return a*b/gcd(a,b); } int main(void){ ll n; cin>>n; vector<ll> a(n); cin>>a[0]; for(ll i=1;i<n;i++){ cin>>a[i]; } ll ans=1; for(ll i=0;i<n;i++){ ans=lcm(ans,a[i]); } cout<<ans<<endl; return 0; }
paizaラーニングのレベルアップ問題集については、ユーザー同士で解答を教え合ったり、コードを公開したりするのは自由としています。
また授業や研修、教材などにも利用できるそうです。