Given a number X how can I find all (or most) numbers that are relatively prime to and less than X?
Ideally I'd like this function to tell me the largest relative primes first.
[Math] How to list all numbers relatively prime to X? (but less than X)
elementary-number-theoryprime numbers
Best Answer
If the number (as you mention in a comment) is about $2^{1024},$ then the task is hopeless. At least 8.4% of the numbers below $X$ are coprime to it (for $X$ of this size), so there are well over $10^{300}$ numbers coprime to and smaller than $X$.
If every atom in the universe was a 1 THz computer that had been operating since the beginning of the universe, you'd only have time to find the first $10^{109}$ numbers. You would be further from your goal than a single electron would be from the universe.