SNCK04: Number of coprimes less than a number (Euclid's number)

general
, ,
1

The practice problem Rational Numbers requires one to find the number of coprimes of a number, say X, less than that number (also called the Euclid’s number of X). Can anyone tell me the method to do this? Is there any formula?

1 Like
2

See for this sort of problem,the method most coder will follow is find first 6 or 7 answer for small input(Either using brute force or manually ) ,and paste them on Famous OEIS sequence search engine site ,(as it saves ample time in finding sequence) ,like I have done here.

The solution for your problem is ::

For input n,answer = Sum( phi(i), i=1…n) - 1.

Where phi is Euler totient function phi(n).

Read this page http://oeis.org/A015614 to know why Sum( phi(i), i=1…n) - 1 is the solution.

5 Likes
3

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int u32;
#define DEBUG 1

const int MAXN = 1000001;

ll totient[MAXN];

void sieve() {

CLEAR(totient);

FOR(i, 2, sqrt(MAXN) + 1) {

    if (totient[i] == 0) {

        totient[i] = (i - 1);

        for (int j = i * 2; j < MAXN; j += i) {

            if (totient[j] == 0)

                totient[j] = j;

            totient[j] = (totient[j] / i) * (i - 1);

        }

    }

}

FOR(i, 1, MAXN)

    totient[i] += totient[i - 1];

}

This is the code block I have used to calculate the totient function. Could someone point out what could be going wrong? I am not able to see why the logic is wrong.