左嘉

用户名：zuojia

访问量：88577

签　名：

等　　级
排　　名	5
经　　验	34534
参赛次数	226
文章发表	72
年　　龄	40
在职情况	在职
学　　校	北京理工大学
专　　业

　　自我简介：

TA的其他文章

信息学奥赛一本通T1444-埃及分数-题解（C语言代码）
浏览：583

用Python爬取本站离线题库
浏览：778

你可能喜欢

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

互质（C语言代码）

　　作者: 左嘉　　　　发表时间：2018-06-22 11:12:01 浏览：2683　|　评论：0　

#### 原题链接：[题目479 - ACM在线评测系统](http://nyoj.top/problem/479 "nyoj在线评测")
#### 原题内容：
**题目描述：**对于给定的整数N(1<=N<=10000)，寻找不大于N并与N互质的正数数量。让我们称两个正整数（比如说，A和B）互质，条件是什么？当且仅当它们的最大公约数是1。例如：若gcd(A,B)=1，A和B是互质的。
**输入描述：**输入包含整数N（注意：程序以文件结束符“EOF”结束输入）。
**输出描述：**输出结果每个数字占一行。
**样例输入：**
9
**样例输出：**
6
#### 解题思路：
按照如下代码所示的思路：
```c
#include<stdio.h>
int gcd(int a,int b);
int main(){
    int i,c,N;
    while(~scanf("%d",&N)){
        if(1==N) printf("1\n"); // 特殊情况
        else{
            c=0;
            for(i=1;i<N;i++)
                if(1==gcd(N,i)) c++; // 为“不大于N与N互质”计数
            printf("%d\n",c);
        }
    }
    return 0;
}
int gcd(int a,int b){
    int r;
    while(b){ // 直到能被余数等分
        r=a%b;
        a=b;
        b=r;
    }
    return a;
} // 求a和b的最大公约数
```
结果是超时。查资料：[欧拉函数](http://www.cnblogs.com/DreamUp/archive/2010/07/24/1784116.html "孟起-博客园")，经过详细的证明过程，得到欧拉函数和质因数的关系：欧拉函数ψ（Ｎ）＝Ｎ｛∏ｐ｜Ｎ｝（１－１/ｐ）。（ｐ是数Ｎ的质因数，若N为质数，ｐ=N）
　　如：
　　ψ（１０）＝１０×（１－１/２）×（１－１/５）＝４；
　　ψ（３０）＝３０×（１－１/２）×（１－１/３）×（１－１/５）＝８；
　　ψ（４９）＝４９×（１－１/７）＝４２。
#### 注意事项：
要求质数或质因子，为了减少时间复杂度，不必每次从更小的数中筛选出是否能使大的数被整除，逆向思维，直接在空间中标记或使用质因子的倍数参与运算。
#### 参考代码：
```c
#include<stdio.h>
#include<string.h>
#define MAX 10000
char prime[MAX+1];
int phi[MAX+1];
int main(){
    int i,j,N;
    memset(prime,(char)1,sizeof(prime));
    prime[0]=prime[1]='\0';
    for(i=2;i*i<=MAX;i++){
        if(prime[i]){ // prime[i]还没有成为从2开始质数的倍数
            for(j=i*i;j<=MAX;j+=i) // 寻找合数
                prime[j]='\0';
        }
    } // 标记MAX以内所有合数
    for(i=1;i<=MAX;i++) phi[i]=i;
    for(i=2;i<=MAX;i++){
        if(prime[i]){
            for(j=i;j<=MAX;j+=i) // i为j的质因数
                phi[j]=phi[j]/i*(i-1);
        }
    } // 从2到MAX寻找每个质数i的倍数j，i即为j的质因数，代入欧拉公式累乘phi[j]*=(1-1/i)
    while(~scanf("%d",&N)) printf("%d\n",phi[N]);
}
```

0.0分

7 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

精彩推荐

C语言训练-字符串正反连接（C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

小九九（C语言代码）

C语言训练-斐波纳契数列（C语言代码）

Hello, world! （C语言代码）

ASCII帮了大忙

WU-蓝桥杯算法提高VIP-交换Easy （C++代码）

求圆的面积（C语言代码）

幸运数（C++代码）

左嘉

TA的其他文章

你可能喜欢

【亲和数】（C语言代码）

【数组的距离】（C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

Lucky Word （C++代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

互质（C语言代码）

评论区

精彩推荐

C语言训练-字符串正反连接（C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

小九九（C语言代码）

C语言训练-斐波纳契数列（C语言代码）

Hello, world! （C语言代码）

ASCII帮了大忙

WU-蓝桥杯算法提高VIP-交换Easy （C++代码）

求圆的面积（C语言代码）

幸运数（C++代码）

左嘉

TA的其他文章

你可能喜欢

【亲和数】 （C语言代码）

【数组的距离】 （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

Lucky Word （C++代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

互质（C语言代码）

评论区

精彩推荐

C语言训练-字符串正反连接 （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

小九九 （C语言代码）

C语言训练-斐波纳契数列 （C语言代码）

Hello, world! （C语言代码）

ASCII帮了大忙

WU-蓝桥杯算法提高VIP-交换Easy （C++代码）

求圆的面积 （C语言代码）

幸运数 （C++代码）

【亲和数】（C语言代码）

【数组的距离】（C语言代码）

　　评论区

C语言训练-字符串正反连接（C语言代码）

小九九（C语言代码）

C语言训练-斐波纳契数列（C语言代码）

求圆的面积（C语言代码）

幸运数（C++代码）