# 工学1号馆

home

## Project Euler 72–Counting fractions

Wu Yudong    August 20, 2018     欧拉计划   552

Counting fractions

Consider the fraction, n/d, where n and d are positive integers. If n < d and HCF(n,d)=1, it is called a reduced proper fraction.

If we list the set of reduced proper fractions for d ≤ 8 in ascending order of size, we get:

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8
It can be seen that there are 21 elements in this set.

How many elements would be contained in the set of reduced proper fractions for d ≤ 1,000,000?

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

d ≤ 1,000,000的最简真分数构成的集合中共有多少个元素？

1、当分母n是素数，则以n为分母的最简真分数的数目为n-1

2、当分母和分子奇偶不同的时候，进一步检查分母和分子的最大公约数

#include<stdio.h>
#include<stdbool.h>
void swap(int* a, int* b)  //交换两值的函数
{
int t;
t = *a;
*a = *b;
*b = t;
}

int gcd(int a, int b)  //求最大公约数函数
{
int r;
if(a < b) swap(&a, &b);
while(b) {
r = a % b;
a = b;
b = r;
}
return a;
}

bool prim(int n) //判断素数函数
{
int i;
for(i = 2; i * i <= n; i++) {
if(n % i == 0)  return false;
}
return true;
}

bool fun(int a, int b)  //判断两整数奇偶是否相同
{
return !((a & 1) & (b & 1));
}

void solve()
{
int i, j, t;
long long count = 0;
for(i = 2; i <= 100000; i++) {
if(i % 2 && prim(i)) {
count += i - 1;
continue;
}
count++;
for(j = 2; j < i; j++) {
if(fun(i,j) && (i % j != 0)) {
t = gcd(i, j);
if(t == 1) count++;  //如果i,j互素，符合
}
}
}
printf("%lld\n", count);
}

int main()
{
solve();
return 0;
}

#include<stdio.h>
#include<stdbool.h>

#define N 1000000

int gcd(int a, int b)  //求最大公约数函数
{
int r;
while(b) {
r = a % b;
a = b;
b = r;
}
return a;
}

bool prim(int n) //判断素数函数
{
int i;
for(i = 2; i * i <= n; i++) {
if(n % i == 0)  return false;
}
return true;
}

bool fun(int a, int b)  //判断两整数奇偶是否相同
{
return !((a & 1) & (b & 1));
}

void solve()
{
int i, j, t;
long long count = 0;
for(i = 2; i <= N; i += 2) {
count++;
for(j = 3; j < i; j += 2) {
t = gcd(i, j);
if(t == 1) count++;
}

}
for(i = 3; i < N; i += 2) {
count++;
if(prim(i)) {
count += i - 1;
continue;
} else {
for(j = 2; j < i; j++) {
if(gcd(i, j)) count++;
}
}

}
printf("%lld\n", count);
}

int main()
{
solve();
return 0;
}

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

#define N 1000001

bool a[N];

void Eratosthenes()
{
int i, M, j;
for(i = 2; i < N; i++) {
a[i] = true;
}
M = (int)sqrt(N);
for(i = 2; i <= M; i++) {
if(a[i]) {
j = i * i;
for(; j < N; j += i)
a[j] = false;
}
}
}

int fun(int n)
{
int t, i, count, j;
t = n / 2;
i = 2;
count = n - 1;
while(i <= t) {
if(a[i]) {
if(n % i == 0) {
count--;
for(j = i; j * i < n; j++) {
count--;
}
}
}
i++;
}
return count;
}

int main()
{
int i;
long long count = 0;

Eratosthenes();

for(i = 2; i < N; i++) {
if(a[i]) {
count += i - 1;
} else {
count += fun(i);
}
}
printf("%lld\n", count);

return 0;
}

算法四：使用欧拉函数

//（Problem 72）Counting fractions
// Completed on Tue, 18 Feb 2014, 14:08
// Language: C11
//
// 版权所有（C）wu yudong
// 博客地址：http://www.wuyudong.com

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<stdbool.h>

#define N 1000001

int phi[N];     //数组中储存每个数的欧拉数

void genPhi(int n)//求出比n小的每一个数的欧拉数(n-1的)
{
int i, j, pNum = 0 ;
memset(phi, 0, sizeof(phi)) ;
phi[1] = 1 ;
for(i = 2; i < n; i++)
{
if(!phi[i])
{
for(j = i; j < n; j += i)
{
if(!phi[j])
phi[j] = j;
phi[j] = phi[j] / i * (i - 1);
}
}
}
}

void solve()
{
int i;
long long ans =0;
for(i = 2; i < N; i++) {
ans += phi[i];
}
printf("%lld\n", ans);
}

int main()
{
genPhi(N);
solve();
return 0;
}