「素因数分解の利用」の編集履歴（バックアップ）一覧に戻る

素因数分解の利用 - (2012/11/27 (火) 19:48:30) のソース

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


*問い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));
 }