一道简单的ACM题，总是超时，各位大侠帮忙看看如何改进。

Question

http://acm.hrbeu.edu.cn/index.php?act=problem&id=1007

我的代码：
#include<iostream>
using namespace std;
int gcd(int m,int n)
{
if(m%n==0)
return n;
else
return gcd(n,m%n);
}
int main()
{
int n;
while(cin>>n)
{
int i,s=0;
if(n==0)
break;
for(i=1;i<n;i++)
if(gcd(n,i)==1)
s++;
cout<<s<<endl;
}
return 0;
}

Answer 1

其实很简单 不要暴搜 会超时 首先将n因式分解 只需将那些不与其质因子互质的数目加起来就行 求于一个质因子互质貌似不难吧 比如49内与不与7互质的数48/7=6；然后加起来用n减去不与n互质的数就是结果了

追问

如何判断一个因子为质因子？
题外话：哥们你大几的，思维怎么这么灵活？

追答

打一个素数表 一万以内的应该足够了

Answer 2

#include<iostream>
using namespace std;
int main()
{
int n;
while(scanf("%d",&n)!=EOF&&n)
{
int i,t=n,m=n,j=0;
for(i=2;i<=t;i++)
while(t%i==0)
{
t=t/i;
if(i!=j)
{
m=m/i*(i-1);
j=i;
}
}
printf("%d\n",m);
}
return 0;
}

Answer 3

5464532463456345645654

Answer 4

//2021 Accepted 252K 16MS C++ 1193B
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct person
{
char fname[50];
char cname[50];
int fage;
};

vector<person> v,v3;

bool cmp(person a,person b)
{
if(a.fage==b.fage)
return strcmp(a.cname,b.cname)<0;
else
return a.fage>b.fage;
}

void fun(char ch[50],int t,int x)
{
int i;
vector<person> v1;
person p;
for (i=0;i<x;i++)
{
if(!strcmp(v[i].fname,ch))
{
strcpy(p.fname,v[i].fname);
strcpy(p.cname,v[i].cname);
p.fage=t-v[i].fage;
v1.push_back(p);
v3.push_back(p);
}
}
for (i=0;i<v1.size();i++)
{
fun(v1[i].cname,v1[i].fage,x);
}
}

int main()
{
person p;
char curname[50];
strcpy(curname,"Ted");
int i,t,x,k=1;
freopen("2021.txt","r",stdin);
cin>>t;
while (t>0)
{
cin>>x;
for (i=0;i<x;i++)
{
cin>>p.fname>>p.cname>>p.fage;
v.push_back(p);
}
cout<<"DATASET "<<k<<endl;
k++;
fun(curname,100,x);
sort(v3.begin(),v3.end(),cmp);
for (i=0;i<v3.size();i++)
{
cout<<v3[i].cname<<" "<<v3[i].fage<<endl;
}
v3.clear();
v.clear();
t--;
}
fclose(stdin);
return 0;
}