[Math] Co Prime Numbers less than N

Question

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?

Answer 1

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