Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
Factorization is not too expensive, since you only need to loop upto the square root of N which should easily fit in 5 seconds. Also, you can easily change the interval to make it within N. – ZeroG Aug 31 '12 at 10:54
@ZeroG but there are 100 N so I dont think factorization will work ,, also what do you mean by "change the interval to make it within N" ? – Loers Antario Aug 31 '12 at 11:06
You can change the interval from (a, b) to (a % N, b % N). Of course, you have to take care of a few cases in here. Also, for 100 N's, you'll be doing the factorization approximately 100 * sqrt(10^9) times, which would be roughly some 10^7 operations. 5 seconds would be more than sufficient for that. – ZeroG Aug 31 '12 at 11:13
A related question came up on MathOverflow,…, you might find something useful in the answers there. – Gerry Myerson Aug 31 '12 at 12:34
I'm not sure why you dismissed the idea of iterating over 100 test cases of $GCD(n,N)$, as I have just done this with a very simple program in Pari/gp on my rather old laptop, and it did the job in well under 1 second using 15 digit numbers. I can time it properly if you wish ... – Old John Aug 31 '12 at 13:02

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.