Relatives POJ

Relatives POJ - 2407

题目链接：https://vjudge.net/problem/POJ-2407#author=0

题目：

给定n是一个正整数，有多少正整数小于n是n的相对素数？ 如果没有整数x> 1，y> 0，z> 0使得a = xy且b = xz，则两个整数a和b是相对素数。
输入
     有几个测试用例。 对于每个测试用例，标准输入包含n <= 1,000,000,000的行。 在最后一种情况下，包含0的行。
产量
     对于每个测试用例，应该有单行输出来回答上面提出的问题。
样本输入

    7
    12
    0

样本输出

    6
    4

思路：一开始打表做发现不行，数据范围太大，会超内存，RE，只能单个求

//
// Created by hanyu on 2019/8/9.
//
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <set>
#include<math.h>
#include<map>
using namespace std;
typedef long long ll;
const int maxn=3e6+7;
#define MAX 0x3f3f3f3f
ll value(ll n)
{
   ll result=n;
   for(int i=2;i*i<=n;i++)
   {
       if(n%i==0)
       {
           result=result/i*(i-1);
           while(n%i==0)
               n/=i;
       }
   }
   if(n>1)
       result=result/n*(n-1);
   return result;
}
int main()
{
    ll n;
    while(~scanf("%lld",&n)&&n)
    {
        printf("%lld
",value(n));
    }
    return 0;
}