一个数在a,b之间且与n互质,求这种数的个数,编程用什么算法
来源：学生作业帮助网 编辑：六六作业网 时间：2025/01/25 04:26:32
一个数在a,b之间且与n互质,求这种数的个数,编程用什么算法
一个数在a,b之间且与n互质,求这种数的个数,编程用什么算法
一个数在a,b之间且与n互质,求这种数的个数,编程用什么算法
1.将a,b之间的数灌入一数组；
2.将n分解因子；
3.将数组中为因子（除1以外的因子）的倍数的数删除；
4.数组中剩余的即为n的互质数
数学不好,⊙﹏⊙b汗
如有算法,同求
//欧几里得的辗转相除法 具体解法!
#include "stdio.h"
int main()
{
long int x,X1,y,Y1,z;
int a,b;
scanf("%d %d",&a,&b);
puts("prime number list:");
for(X1=a;X1<=b;X1++) ...
全部展开
//欧几里得的辗转相除法 具体解法!
#include "stdio.h"
int main()
{
long int x,X1,y,Y1,z;
int a,b;
scanf("%d %d",&a,&b);
puts("prime number list:");
for(X1=a;X1<=b;X1++)
for(Y1=a;Y1<=b;Y1++)
{
x=X1;
y=Y1;
z = x % y;
while(z != 0)
{
//变换变量的值
x=y;
y=z;
z=x % y;
}
if(y==1)
{printf("%4d %4d\t",X1,Y1);}
}
return 0;
}
程序已调试通过，
输入1 30 即可获得1~30之间的互质数
收起
公因数只有1的两个数，叫做互质数
伪代码:
count = 0
for i in [a..b]:
if gcd(i,n)==1: /*欧拉的辗转反除定义最大公因子函数gcd*/
count++