# List of numbers without common factors with a certain number

Is there any function in Mathematica which directly gives an array of integer numbers with no common factor with a certain integer number?

For example, all the integer numbers between 0 and 1728, which do not have any common factor with 12 (apart from the common factor one ofcourse.)

I know how to make a program to do that, I just wonder wether there is a comand to do it.

-
why don't you show us your program... –  bill s Apr 4 '13 at 16:16
Select[Range[0, 1728], CoprimeQ[#, 12] &] –  Ｊ. Ｍ. Apr 4 '13 at 16:27
@J.M. thnks thanks! –  Mencia Apr 4 '13 at 16:28
@J.M. I think you want that predicate to be GCD[#, 12] == 1 & –  Daniel Lichtblau Apr 4 '13 at 16:37
@J.M. Was your comment previous to my answer? If it was, please accept my apologies. –  belisarius Apr 5 '13 at 13:52
show 1 more comment

Select[Range[0, 1728], CoprimeQ[12, #] &]

-
thanks @belisarius! –  Mencia Apr 4 '13 at 16:46
Why not pump it up using its listability, Pick[#, CoprimeQ[#, 12]] &@Range[0, 1728] –  Rojo Apr 4 '13 at 19:22
Nheee, it only seems barely faster –  Rojo Apr 4 '13 at 19:30
@Rojo The timing was worst here –  belisarius Apr 4 '13 at 19:30

Here are a couple of ways. One is cribbed from J.M. To indicate speed I show for the range (0...10^6).

I'll view this part as preprocessing.

n = 10^6;
div = 12;
fax = FactorInteger[div][[All, 1]];
sqfreeprod = Times @@ fax

Timing[r1 = Select[Range[0, n], GCD[#, sqfreeprod] == 1 &];]

(* Out[562]= {1.230000, Null} *)

Timing[
avoid = Map[Range[0, n, #] &, fax];
r2 = Complement[Range[0, n], Sequence @@ avoid];]

(* Out[563]= {0.040000, Null} *)

r1 === r2

(* Out[564]= True *)


If using numbers with many factors for div then the gcd-based approach might be faster.

-
+1 This is an adaptation of the sieve of Eratosthenes. There is a time-space tradeoff: as the number of prime divisors of div grows, the sieve becomes less competitive. –  whuber Apr 5 '13 at 13:49