素因数分解の利用 - c21coterie @ ウィキ

大学への数学　マスター・オブ・整数

問い1-1-1～３

問い1-1～３までを解くコード。
問い1-１　1500の約数の和
問い1-２　１５００の約数で２１と互いに素なもの
問い1-３　１５００の約数を全て掛けると幾らになるか？

#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;
}
if(n!=1)re*=(n+1);
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]++;
	}
}
if(n!=1)memo[n]=1;
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]--;
	}
}
if(n!=1&&memo.find(n)!=memo.end())memo[n]--;
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;
}
if(n!=1)re++;
return re/2;
}
int main(){
printf("%d\n",yakusuuSum(1500));
printf("%d\n",yakusuuCount(1500,21));
printf("1500^%d\n",yakusuuMult(1500));
}

問い２-1
1～100までの自然数のうち約数の個数が偶数個になるもの。
問い２-２の発展問題、ｎ個の約数を持つ最小のｘを見つける関数を考え中。

#include<stdio.h>
#include<math.h>
int calc1(int n){
return n-(int)sqrt(n);
}
int main(){ 
printf("問い2-1答え　%d\n",calc1(100));	
}

問い３-1
１～２００までの数字が書かれたカードを一定のルールでひっくり返す問題。
問い２と同じ計算で片が付きます。

#include<stdio.h>
#include<math.h>
int calc1(int n){
  return n-(int)sqrt(n);
}
int main(){ 
  printf("問い3答え　%d\n",calc1(200));	
}

問い4
有る整数の約数を全て足すと168になり、約数の逆数を全て足すと2.8になる数を求める問題。

#include<stdio.h>
#include<math.h>
#include<map>
int calc1(double n,double r){
return (int)(n/r+0.1);//多分誤差的に言って大丈夫かと
}
int main(){
printf("%d",calc1(168,2.8));
}