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

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

問い2-1

3/ｘが丁度小数点以下３桁となる既約分数は何個あるか？

#include<stdio.h>
int yakusuuCount(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;
}
int calc1(int n,int keta){
return (yakusuuCount(n))*((keta+1)+(keta));
}
int main(){
printf("%d",calc1(3,3));
}

問い２-２

(384-12m)が自然数となるようなｍを全て求めよ。
√(7n)<42となるｎの和を全て求めよ。

#include<stdio.h>
#include<math.h>
void calc(int m,int n){
for(int i=1;i*n<m;i++){
	int k=sqrt(m-n*i);
	if(k*k==m-n*i)printf("%d ",i);
}
}
int calc2(int n,int m){
int re=0;//本当は素因数分解をりようして桁あふれが起きないように計算するのだけどまあ手抜き
for(int i=1;sqrt(n*i)<m;i++){
	int k=sqrt(n*i);
	if(k*k==n*i&&k<m)re+=i;
}
return re;
}
int main(){
calc(384,12);
printf("\n%d ",calc2(7,42));
}

問い２-３

24a=90b=c^2を満たすｃを求めよ。

#include<stdio.h>
#include<map>
#include<math.h>

std::map<int,int> yakusuuCount(int n){
std::map<int,int> re;
for(int i=2;i*i<=n;i++){
	int count=0;
	while(n%i==0){
		n/=i;
		count++;
	}
	if(count>0)re[i]=count;
}
if(n!=1)re[n]=1;
return re;
}
int calc(int n,int m){
std::map<int,int> m1,m2;
std::map<int,int>::iterator it;
m1=yakusuuCount(n);
m2=yakusuuCount(m);
for(it=m2.begin();it!=m2.end();it++){
	int p=(*it).first;
	int p2=(*it).second;
	if(m1.find(p)==m1.end()||m1[p]<p2){
		m1[p]=p2;
	}
}
int c=1;
for(it=m1.begin();it!=m1.end();it++){
	int p=(*it).first;
	int p2=(*it).second;
	if(p2%2==1)p2++;
	c*=pow(p,p2/2);
}
return c;
}
int main(){
printf("%d",calc(24,90));
}

問い2-4

n^2/1250,n^3/45,n^4/768の全てが整数となる最小のｎを求めよ。

#include<stdio.h>
#include<map>
#include<math.h>
std::map<int,int> yakusuuCount(int n){
std::map<int,int> re;
for(int i=2;i*i<=n;i++){
	int count=0;
	while(n%i==0){
		n/=i;
		count++;
	}
	if(count>0)re[i]=count;
}
if(n!=1)re[n]=1;
return re;
}
void calc2(std::map<int,int> m,std::map<int,int>& re,int n){
std::map<int,int>::iterator it;
for(it=m.begin();it!=m.end();it++){
	int p=(*it).first;
	int p2=((*it).second-1)/n+1;
	if(re.find(p)==re.end()||re[p]<p2){
		re[p]=p2;
	}
}
}
int calc(int a,int b,int c){
std::map<int,int> m1,m2,m3,ans;
std::map<int,int>::iterator it;
m1=yakusuuCount(a);
m2=yakusuuCount(b);
m3=yakusuuCount(c);
calc2(m1,ans,2);
calc2(m2,ans,3);
calc2(m3,ans,4);
int re=1;
for(it=ans.begin();it!=ans.end();it++){
	re*=pow((*it).first,(*it).second);
}
return re;
}
int main(){
printf("%d",calc(1250,45,768));
}

問い2-5

100！は何個の２で割り切れるか、また末尾に何個０が並ぶか。

#include<stdio.h>
int main(){
int count5=0,count2=0;
for(int i=1;i<=100;i++){
	int n=i;
	while(n%2==0){
		n/=2;
		count2++;
	}
	while(n%5==0){
		n/=5;
		count5++;
	}
}
printf("%d %d",count2,count5);
}