Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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.

share|improve this question
    
why don't you show us your program... –  bill s Apr 4 '13 at 16:16
3  
Select[Range[0, 1728], CoprimeQ[#, 12] &] –  J. M. 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

2 Answers 2

up vote 5 down vote accepted
Select[Range[0, 1728], CoprimeQ[12, #] &]
share|improve this answer
    
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.

share|improve this answer
1  
+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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.