Question

一道小小的ACM题，用C或者C++写，提交老是说超时，求高人指点迷津

源码：#include "stdio.h"

int main()
{
int n,i = 0;
scanf("%d",&n);
while(n)
{
int j,a = 1;
int t = n;
for(j = 2;j < n;j++)
if(t % j == 0)
{
t= t / j;
a= a * (j - 1);
}
if(a == 1)
a = t - 1;
else
a =a * t;
printf("%d\n",a);
scanf("%d",&n);
}
return 0;
}
原题：
LK的数学题
时间限制：1000 ms | 内存限制：65535 KB
难度：3

描述
LK最近遇到一个问题，需要你帮她一下。一个整数n，求[1,n)中，和n互素的数的个数。

输入
多组测试数据，每一行有一个整数n（n<1000000001），0表示输入结束。
输出
小于n同时和n互素的整数的个数
样例输入

7
12
0

样例输出

6
4

Answer 1

这题是考欧拉函数的应用

参考代码：
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
unsigned euler(unsigned x)
{
unsigned i, res=x;
int sum = (int)sqrt(x * 1.0) + 1;
for (i = 2; i < sum; i++)
if(x%i==0) {
res = res / i * (i - 1);
while (x % i == 0) x /= i; // 保证i一定是素数
}
if (x > 1) res = res / x * (x - 1);
return res;
}
int main()
{
int n;
while (scanf("%d",&n)&&n)
{
printf("%d\n",euler(n));
}
return 0;
}

Answer 2

和7互素的就6个啊怎么会输出12自己算一下就知道我这里有一个c++编的你看一下把
#include<iostream>
using namespace std;
void main(){
long a;
int k=0,loop=1;
cin>>a;
while(loop){
for(long i=2;i<a;i++)
if(a%i==0)k++;
cout<<k<<endl;
k=0;
cin>>loop;

}
}
如果你要输出上面的东西你可以在输出结果的时候再乘以一个2
望及时采纳~

Answer 3

估计是算法不对