2
$\begingroup$

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

  • 0
    @ZeroG mmmmm I tried doing the (a % N, b % N) like for 5 on(11,21) that makes it 5 on (1,1) !! I think am doing it wrong ,, but let's say that we were able to change the interval from (a,b) to sth smaller (q,w) what if there were 50 primes in (a,b) and our N was prime then N is definitely co-prime to all of them won't we lose them when we convert to (q,w) ??2012-08-31

0 Answers 0