「素因数分解の利用」の編集履歴(バックアップ)一覧はこちら
素因数分解の利用 - (2012/11/27 (火) 18:08:15) の1つ前との変更点
追加された行は緑色になります。
削除された行は赤色になります。
大学への数学 マスター・オブ・整数
問い1-1~3までを解くコード。
問い1 1500の約数の和
問い2 1500の約数で21と互いに素なもの
問い3 1500の約数を全て掛けると幾らになるか?
#include<stdio.h>
#include<map>
int yakusuuSum(int n){
int mul,k,re=1;
for(int i=2;i*i<=n;i++){
mul=k=1;
while(n%i==0){
n/=i;
k*=i;
mul+=k;
}
re*=mul;
}
return re;
}
int yakusuuCount(int n,int a){
std::map<int,int> memo;
for(int i=2;i*i<=n;i++){
while(n%i==0){
n/=i;
if(memo.find(i)==memo.end())memo[i]=0;
memo[i]++;
}
}
for(int i=2;i*i<=a;i++){
while(a%i==0){
a/=i;
if(memo.find(i)!=memo.end()&&memo[i]>0)memo[i]--;
}
}
int re=1;
for(std::map<int,int>::iterator it=memo.begin();it!=memo.end();it++){
re*=((*it).second+1);
}
return re;
}
int yakusuuMult(int n){
int re=1;
for(int i=2;i*i<=n;i++){
int count=1;
while(n%i==0){
n/=i;
count++;
}
re*=count;
}
return re/2;
}
int main(){
printf("%d\n",yakusuuSum(1500));
printf("%d\n",yakusuuCount(1500,21));
printf("1500^%d\n",yakusuuMult(1500));
}
大学への数学 マスター・オブ・整数
問い2-2の発展問題n個の約数をもつ最小の数xを求める問題を考え中。
問い1-1~3までを解くコード。
問い1-1 1500の約数の和
問い1-2 1500の約数で21と互いに素なもの
問い1-3 1500の約数を全て掛けると幾らになるか?
#include<stdio.h>
#include<map>
int yakusuuSum(int n){
int mul,k,re=1;
for(int i=2;i*i<=n;i++){
mul=k=1;
while(n%i==0){
n/=i;
k*=i;
mul+=k;
}
re*=mul;
}
return re;
}
int yakusuuCount(int n,int a){
std::map<int,int> memo;
for(int i=2;i*i<=n;i++){
while(n%i==0){
n/=i;
if(memo.find(i)==memo.end())memo[i]=0;
memo[i]++;
}
}
for(int i=2;i*i<=a;i++){
while(a%i==0){
a/=i;
if(memo.find(i)!=memo.end()&&memo[i]>0)memo[i]--;
}
}
int re=1;
for(std::map<int,int>::iterator it=memo.begin();it!=memo.end();it++){
re*=((*it).second+1);
}
return re;
}
int yakusuuMult(int n){
int re=1;
for(int i=2;i*i<=n;i++){
int count=1;
while(n%i==0){
n/=i;
count++;
}
re*=count;
}
return re/2;
}
int main(){
printf("%d\n",yakusuuSum(1500));
printf("%d\n",yakusuuCount(1500,21));
printf("1500^%d\n",yakusuuMult(1500));
}
問い2-1
1~100までの自然数のうち約数の個数が偶数個になるもの。
問い2-2の発展問題、n個の約数を持つ最小のxを見つける関数を考え中。
#include<stdio.h>
#include<math.h>
int calc1(int n){
return n-(int)sqrt(n);
}
int main(){
printf("問い2-1答え %d\n",calc1(100));
}