オイラー関数 - c21coterie @ ウィキ

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

問い5-1-1と5-1-2と5-2

問い5-1　504以下で504と互いに素な数の個数とその合計。
問い5-2
線分ABに２等分点、３等分点、、１４０等分点を順番に付け加えていく時、１４０等分点では何個新しい点が増えるか？

#include<stdio.h>
int phi(int n){
double re=n;
for(int i=2;i*i<=n;i++){
	int count=0;
	while(n%i==0){
		n/=i;
		count++;
	}
	if(count!=0)re*=(1.0-1.0/i);
}
if(n!=1)re*=(1.0-1.0/n);
return re+0.5;
}
void calc(int n){
int k=phi(n);
printf("問い1-1と1-2の答え%d %d",k,k/2*n);
}
int main(){
calc(504);
printf(" 問い２の答え%d",phi(140));
}

問い5-3 5-4

問い5-3 0<x<=10 0<y<=10の格子点に原点から線分を伸ばしたとき、線分上に格子点が並ばない線分の数は何本あるか？
問い5-4 正６００角形の頂点を一定間隔で飛ばして線分を引いていき最初の点に戻るとき何通りの線の引き方があるか？

#include<stdio.h>
int phi(int n){
double re=n;
for(int i=2;i*i<=n;i++){
	int count=0;
	while(n%i==0){
		n/=i;
		count++;
	}
	if(count!=0)re*=(1.0-1.0/i);
}
if(n!=1)re*=(1.0-1.0/n);
return re+0.5;
}
void calc(int n){
int ans=0;
for(int i=2;i<=n;i++){
	ans+=phi(i);
}
printf("問い5-３の答え%d",ans*2+1);
}
int main(){
calc(10);
printf("\n問い5-4の答え%d",phi(600)/2);
}