[선택 전 문제 정리] [POJ 2407] Relatives (오로라 함수)

제목 링크
http://poj.org/problem?id=2407
제목 의 대의
n, 오로라 함수 구하 기ϕ(n)
사고의 방향
두 가지 방법 이 있 습 니 다. 1. O (n) 선형 체 법 은 n 이 매우 작 지만 오로라 함 수 를 구 하 는 횟수 가 많은 곳 에 적합 합 니 다.이 문 제 는 n 이 너무 커서 TLE 입 니 다.2. 오로라 함수 공식 에 따라 n 의 질 인 수 를 분해 하면 n 이 비교적 크 지만 오로라 의 횟수 가 적은 곳 에 적합 하고 본 문제 에 적합 합 니 다.
코드
1. O (n) 선형 체

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>

#define MAXN 1000

using namespace std;

bool isPrime[MAXN];
int fai[MAXN]; //    
int prime[MAXN],tot=0; //  

void GetEular()
{
    memset(isPrime,true,sizeof(isPrime));
    fai[1]=1;
    tot=0;
    for(int i=2;i<MAXN;i++)
    {
        if(isPrime[i])
        {
            prime[++tot]=i;
            fai[i]=i-1;
        }
        for(int j=1;j<=tot;j++)
        {
            if(i*prime[j]>MAXN) break;
            isPrime[i*prime[j]]=false;
            if(i%prime[j]==0)
            {
                fai[i*prime[j]]=fai[i]*prime[j];
                break;
            }
            else
                fai[i*prime[j]]=fai[i]*(prime[j]-1);
        }
    }
}

int main()
{
    GetEular();
    int n;
    while(scanf("%d",&n)!=EOF&&n)
    {
        printf("%d
",fai[n]);
    }
    return 0;
}

2. 분해 n 의 질량 인수

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>

#define MAXN 1000

using namespace std;

int fai(int n)
{
    int ans=n;
    for(int i=2;i<=n;i++)
    {
        if(n%i==0)
        {
            ans=ans/i*(i-1);
            while(n%i==0) n/=i;
        }
    }
    return ans;
}

int main()
{
    int n;
    while(scanf("%d",&n)!=EOF&&n)
    {
        printf("%d
",fai(n));
    }
    return 0;
}