ACMSGURU 102 - Coprimes

Reck Zhang

发布于 2021-08-11 11:10:02

4120

Coprimes

Problem Description

For given integer N (1<=N<=10^4) find amount of positive numbers not greater than N that coprime with N. Let us call two positive integers (say, A and B, for example) coprime if (and only if) their greatest common divisor is 1. (i.e. A and B are coprime iff gcd(A,B) = 1).

Input

Input file contains integer N.

Output

Write answer in output file.

Sample Input

Sample Output

Solution

#include <bits/stdc++.h>

int main() {
    std::ios::sync_with_stdio(false);

    int n;
    std::cin >> n;

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

    if(n > 1) {
        ans -= ans / n;
    }

    std::cout << ans << std::endl;

    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2019-10-24，如有侵权请联系 cloudcommunity@tencent.com 删除

file