How many co-primes are there for a big integer $N$ over a specified interval ? bounds of $N$ are $[1,10^9]$ and the interval is $[a,b]$ where ($1\leq a\leq b \leq 10 ^{15}$) and there are $100$ testcases of $N$, this is a programming problem actually. Trying "Euler Phi" in its standard formula:
$\varphi(n)=n\prod_{p|n}\left(1-\frac 1p\right)$
wont work since we need to factor the Number and that needs generating primes , and since $N$ could reach $10^9$ and there is a time limit for computing, I think 5 seconds. then generating primes is not a good idea .
and looping through $GCD(n,N)$ won't work as there are $100$ testcases and this will take a lot of time , also trying Fourier transform of Phi will take even longer .
so how can I solve this ? thanks in advance ..