C语言:互质
2024-09-01 15:53:00
今天遇到一道奇怪的程序题,和平常的不同。同样都是互质,但是一般的题目都是判断两个数字是否互质,但这道题则是给定一个数字n,要求输出所有小于等于n的与n互质的数,题目已经在下面给出:
质数与互质概念不是同一个,质数指的是一个数仅有1和它自己本身可以被整除;而互质则指的是两个数只有1是共同的因数,有些人可能会将两者混为一谈。本篇文章是以互质为主题,接下来以互质作为主要内容,不过不得不说,这两者的核心都是一样的,采取欧几里得算法(又叫辗转相除法),通常用gcd表示,欧几里得算法应用范围非常广泛,在今后的blog中我会专门写一篇文章来讲欧几里得算法。
言归正传,这道题有多行测试数据,因此我们可以用while语句作为循环,考虑到会超时,于是我打算用自定义函数:
被除数a和除数b相除取余数c,将余数c给除数b,除数b给被除数a,以此往复,直到直到b为0,作为结束的标志。
本题考察的是自定义函数,其中欧几里得算法非常重要。
以下是完整代码:
#include <stdio.h>
int Gcd(int m,int n)
{
int o;
while(n>)
{
o=m%n;
m=n;
n=o;
}
return m;
}
int main()
{
int a,i,b,s;
while(scanf("%d",&a)!=EOF)
{
if(a==)
{
printf("1\n");
}
else{
s=;
for(i=;i<a;i++)
{
b=Gcd(i,a);
if(b==)
{
s++;
}
}
printf("%d\n",s);
}
}
return ;
}
最新文章
- Bzoj2683 简单题 [CDQ分治]
- ASP.NET中进行消息处理(MSMQ) 二(转)
- Luci中cbi控件类型总结
- TCP的3次握手和4次挥手
- Javascript中函数的四种调用方式
- share干什么的
- rabbitMQ 笔记
- (经典)tcp粘包分析
- 使用OpenXml实现生成数据字典文档(beta)
- Objective-C中math.h数学计算公式介绍
- 解决,Incorrect table definition; there can be only one auto column and it must be defined as a key
- 万马齐喑究可哀-中文编程的又一波";讨论";
- 怎么让html中 还是显示<;button>; 而不进行编译
- shell练习题4
- HTTP协议快速入门指南
- 【转】c# [Serializable]的作用
- [Android源码]Android源码之高仿飞鸽传书WIFI热点搜索与创建(一)
- Centos安装FTP服务器和配置
- 福大软工1816 - 第八次作业(课堂实战)- 项目UML设计
- python---django中权限框架设计