Co Prime Numbers less than N I need to find all the numbers that are coprime to a given $N$ and less than $N$.
Note that $N$ can be as large as $10^9.$ For example, numbers coprime to $5$ are $1,2,3,4$.
I want an efficient algorithm to do it. Can anyone help? 
 A: What you want is Euler's totient function. 
You'll find a formula there.
A: Once you find the prime factors $p_1, \ldots, p_k$ of $N$, you could use a sieve: start with $1 \ldots N-1$, delete all multiples of $p_1$, then all multiples of $p_2$, etc.  What's left is coprime to $N$.
A: First find the factors of it by factorisation 
second get the prime numbers involved in that say $(a,b,\ldots)$.
E.g., $18=(2^1)(3^2)$. The prime factors are $2$ and $3$.
Third formula:
     $$\text{No. of coprimes to $N$}= N(1-1/a)(1-1/b)\cdots$$
A: I assume you know how to implement sets. We will only add numbers $<N$ to the set so any bit representation is okay.
If you know that the primes dividing $N$ then the following works:
S={} // Empty sets
for p in primes dividing $N$
   add p,2p,3p... to S
end for

If you do not know the factors of $N$ then here is one not very efficient (but not terribly inefficient) way to do it.
S={} // Empty set
for k=2 to N
    if k is not in the set S then
          if gcd(k,N) > 1 then
             Add the following to S: k, 2k, 3k, 4k    
           end if
     end if
 end for

Now all the elements in $S$ are not co prime to  N, so its complement is the numbers you want
