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?
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.
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.