# How can I write the natural numbers less than $n$ that are coprime to $n$? [duplicate]

How can I write the natural numbers less than $n$ that are coprime to $n$?

## marked as duplicate by MarcoB, Michael E2, dr.blochwave, m_goldberg, ciaoSep 9 '15 at 4:40

• Please, post code, not images. After you do this you can read and format your code properly – Sektor Sep 8 '15 at 12:58
• Greetings! Make the most of Mma.SE and take the tour. Help us to help you, write an excellent question. Edit if improvable, show due diligence, give brief context, include minimum working examples of code and data in formatted form. As you receive give back, vote and answer questions, keep the site useful, be kind, correct mistakes and share what you have learned. – rhermans Sep 8 '15 at 13:30

This should be faster than existing answers:

With[{r = Range[#]}, Pick[r, CoprimeQ[r, #]]] &[10^7]


You can use Select to choose the correct elements out of a Range.

n = 10;
Select[Range[n], GCD[#, n] == 1 &]

(*--> {1, 3, 7, 9}*)


The functionalized form GCD[#, n] == 1 & is a pure Function and returns either True or False when applied as e.g. GCD[#, n] == 1 &[4].

The above is the 'ideal' Mathematica way, but it might not scale particularly well as you need to write down the entire list of numbers first. Your intuition is correct that you can go through the range up to n and only keep the numbers you want, and this is done using Sow and Reap as follows.

Reap[
Do[
If[GCD[i, n] == 1, Sow[i]]
, {i, n}]
]
(*--> {Null, {{1, 3, 7, 9}}}*)


The output from Reap is the output from the Do (which is Null) and a list of all the Sowed items of the different tags in use. This is faster than the above but only slightly so.

• I did some quick-and-dirty timing, and it seems to me that the Do loop solution is faster for smaller ranges, but becomes slower for very large ranges (e.g. n = 10000000). Do you see the same? – MarcoB Sep 8 '15 at 14:59
• @Marco One should really use David's approach. If there's an inbuilt function it will likely work better. I mentioned the Reap/Sow pair to formalize what the OP was trying to do but I don't think it's a great idea. – Emilio Pisanty Sep 8 '15 at 15:08

Slight improvement over epistanty's first answer:

n = 10;
Select[Range[n], CoprimeQ[#, n] &]


It scales better than his first solution as well:

Timing[Select[Range[10^7], CoprimeQ[#, 10^7] &];]


{18.4778, Null}

Timing[Select[Range[10^7], GCD[#, 10^7] == 1 &];]


{23.3811, Null}

For large values of n you could use Compile.

CoprimeList[n_] := CoprimeListcompiled[n, FactorInteger[n][[All, 1]]]

CoprimeListcompiled = Compile[{{n, _Integer}, {ps, _Integer, 1}},
Module[{S = Range[n]},
Do[
S[[k*i]] = 0,
{k, ps}, {i, 1, n/k}
];
Select[S, Positive]
],
CompilationTarget -> "C",
RuntimeOptions -> "Speed"
];

CoprimeList[10^8] // Length // AbsoluteTiming

{2.05012, 40000000}

EulerPhi[10^8]

40000000