Find all numbers between 2 and 100 co-prime to a given number

Question

Your program will be given a number as input. Your challenge is to output all the numbers between 2 and 100 inclusive that are co-prime to the given number. (Two numbers are co-prime if their GCD is 1.) If no numbers between 2 and 100 are co-prime to the given number, the program shall not output anything.

The program must receive the number from STDIN, and the output must be a list of numbers separated by a comma and a space.

Contest closes June 14th, 2014, two weeks from now. The shortest solution wins.

Examples (here the range is from 2 to 20):

3:

2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20

12:

5, 7, 11, 13, 17, 19

9699690:

(No output: no numbers between 2 and 20 are co-prime to 9699690).

EDIT: Esoteric languages (e.g. J or GolfScript) are now being assessed separately from non-esoteric languages. This is to make the challenge fair.

Answer 1

CJam, 23 bytes

101,:N2>q~mf{N%-}/", "*

Try it online. Paste the Code, type an integer in Input and click Run.

Example

$ cjam factor.cjam <<< 210
11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

How it works

101,:N # Push the array [ 0 ... 100 ] and save it in “N”.
2>     # Remove 0 and 1 from the array.
q~mf   # Read from STDIN, interpret the input and factorize the resulting integer.
{      # For each prime factor:
  N%   # Collect all multiples of the prime factor in an array.
  -    # Apply set difference with the array on the stack.
}/     # This leaves only integers that are coprime with the input.
", "*  # Join by commas and spaces.

Answer 2

Haskell, 76 characters

main=do n<-readLn;putStrLn.drop 2$[show k|k<-[2..100],gcd k n<2]>>=(", "++)

Answer 3

GolfScript - 36

~:x;101,2>{.x{.@\%.}do;1>{;}*}%", "*

Explanation:

~ evaluates the input to a number
:x; assigns the number to variable x
101,2> makes an array [2 ... 100]
{...}% applies the block to each array element, resulting in a modified array
.x duplicates the current number (from 2 to 100) then pushes x
{.@\%.}do; calculates the gcd (see the GolfScript home page)
1> checks if the gcd was greater than 1
{;}* executes the block if the condition was true; the block (;) pops the current number from the stack, thus taking it out of the array
", "* joins the resulting array using the ", " separator

Answer 4

Python 2.7 - 87 bytes

from fractions import*
x=input()
print', '.join(`i`for i in range(2,101)if gcd(x,i)==1)

This is very similar to qwr's answer here, I shaved off some bytes but the changes were too substantial to fit in a comment. Full respect goes to them.

Modifications:

• Removed unnecessary space in from fractions import * for one byte.
• Moved the whole thing to python 2.7. I couldn't actually get the original answer to run on my machine because input() returns a string in python 3. The only thing that was specific to python 3 in the answer was defining the output format in the print function...
• ...which I changed anyway. The original answer looped through all the numbers and printed them out if the met the requirements. Here, I throw the whole thing in a generator function (with the output wrapped in backticks so we get a string) and join the numbers together, which saves bytes and means we don't have to use the "technically rules-valid" output format the original answer used (23 ,29 ,31 ,37... is a list of numbers separated by a comma and a space, but it doesn't waste any characters in my version to print out 23, 29, 31... like the OP was probably expecting).

Answer 5

Ruby, 52 46 (43 + 3 for " -p" option)

Now does beat it J (barely). Caveat: doesn't exit after outputting (you can actually keep giving more inputs after the first).

$_=(2..100).select{|w|w.gcd(eval$_)<2}*", "

Answer 6

Julia - 70 69 68 characters

i=int(readline());print(join(find([gcd(i,x)<2 for x=2:100])+1,", "))

Saved a character by using a list comprehension rather than a map, pretty much thanks to not needing the dotted .==. I suspect that I can do better, still.

Second edit saved another character by using <2 rather than ==1, as gcd can't produce a number less than 1 (except when both inputs are 0, which cannot happen with this code), and must produce an integer.

Old version:

i=int(readline());print(join(find(map(x->gcd(i,x),2:100).==1)+1,", "))

Note that int is Int64 (assuming a 64 bit machine), meaning that you can't actually have a number big enough to be non-coprime to every number between 2 and 100. To have it accept arbitrary-size integers, you need to replace int with BigInt, for a total of 73 characters.

Answer 7

Vyxal 3, 6 bytes

₅ḢΩ?ĠḂ

Try it Online!

RIP H flag

Answer 8

JavaScript (ECMAScript 6) - 82 Characters

g=(a,b)=>b?g(b,a%b):a;f=x=>[k for(y in[...Array(99)])if(g(x,k=+y+2)<2)].join(', ')

Explanation:

Firstly a recursive function g to calculate the gcd:

g=(a,b)=>b?g(b,a%b):a;

Secondly, a function f taking a single argument x:

• Array(99) - Start with an uninitialised array of length 99.
• [...Array(99)] - Use the ... spread operator to turn it into an array of 99 elements each initialised to undefined.
• [+y+2 for(y in[...Array(99)])] - Use Array Comprehension to map the array of undefined values to an array of integers 2..100.
• [k for(y in[...Array(99)])if(g(x,k=+y+2)<2)] - Add an additional restriction to only include those values where GCD(x,value) is 1.
• .join(', ') - at the end return it as a comma-space delimited string to meet the requirement of outputting nothing if there are no matches.

Alternative

Taking input from a prompt (87 characters):

x=prompt(g=(a,b)=>b?g(b,a%b):a);[k for(y in[...Array(99)])if(g(x,k=+y+2)<2)].join(', ')

Answer 9

J (20):

Not quite complying with the rules as they are now, but hey... JS isn't either ;)

}.(1=a+.i.101)#i.101

Showcase:

   a=:3
   }.(1=a+.i.101)#i.101
2 4 5 7 8 10 11 13 14 16 17 19 20 22 23 25 26 28 29 31 32 34 35 37 38 40 41 43 44 46 47 49 50 52 53 55 56 58 59 61 62 64 65 67 68 70 71 73 74 76 77 79 80 82 83 85 86 88 89 91 92 94 95 97 98 100
   a=:12
   }.(1=a+.i.101)#i.101
5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67 71 73 77 79 83 85 89 91 95 97
   a=:9699690
   }.(1=a+.i.101)#i.101
23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

Deconstruction:

Remember that J programs start at the back:

   i.101
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88...
   a=:12
   a+.i.101 NB. Takes GCD
12 1 2 3 4 1 6 1 4 3 2 1 12 1 2 3 4 1 6 1 4 3 2 1 12 1 2 3 4 1 6 1 4 3 2 1 12 1 2 3 4 1 6 1 4 3 2 1 12 1 2 3 4 1 6 1 4 3 2 1 12 1 2 3 4 1 6 1 4 3 2 1 12 1 2 3 4 1 6 1 4 3 2 1 12 1 2 3 4 1 6 1 4 3 2 1 12 1 2 3 4
   1=a+.i.101
0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0
   (1=a+.i.101)#i.101
1 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67 71 73 77 79 83 85 89 91 95 97
   }.(1=a+.i.101)#i.101
5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67 71 73 77 79 83 85 89 91 95 97

Answer 10

Javascript (ES5) - 92 91

This solution runs in the Spidermonkey commandline shell. It takes input from STDIN (as per the rules).

with([])for(a=readline(b=1);b++<99||print(join(', '));--c||push(b))for(c=a,d=b;d;)d=c%(c=d)

Here is a solution that runs in the browser console and takes input from prompt and outputs with alert: (89 bytes)

with([])for(a=prompt(b=1);b++<99||alert(join(', '));--c||push(b))for(c=a,d=b;d;)d=c%(c=d)

If implicit printing in the browser console is allowed, it can go even further: (82 bytes)

for(o=[],a=prompt(b=1);b++<99;--c||o.push(b))for(c=a,d=b;d;)d=c%(c=d);o.join(', ')

Answer 11

Haskell - 105

import Data.List
main=do
 x<-getLine
 putStrLn.intercalate", ".map show$filter((1==).gcd(read x))[2..100]

Quite obvious if you can understand Haskell. :)

Answer 12

Lua, 126

Now it's 2 times longer, but it actually works.

c=io.read()function g(a,b)return b~=0 and g(b,a%b) or tonumber(a) end for i=2,100 do if g(i,c)<2 then io.write(i,', ') end end

---

Lua, 63

Not much better, but still...

c=io.read()for i=2,100 do if i%c>0 then io.write(i,', ')end end

Lua, 64

c=io.read()for i=2,100 do if i%c>0 then io.write(i..', ')end end

Answer 13

Pyke, 9 bytes (noncompeting)

TXSt#.H1q

Try it here!

TX        -   10**2 (100)
  St      -  range(2, ^)
    #     - filter(^, V)
     .H   -   highest_common_factor(i, input)
       1q -  ^ == 1

Answer 14

Vyxal H, 44 bits^v2, 5.5 bytes

ɽḢ'?ġ1=

Try it Online!

Bitstring:

00100110011110110000000000001000100000100111

Because vyxal 3 is missing a lot of numerical operations :p

Answer 15

Japt, 7 bytes

Lõ ÅfjU

Try it here

Answer 16

Sage, 79

A boring answer, since I'm not in the mood of writing an interesting one.

l=[]
n=input()
for i in range(2,101):
 if gcd(i,n)==1:l+=[i]
print str(l)[1:-1]

Sample outputs:

sage: %runfile coprimelist.py
3
2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 25, 26, 28, 29, 31, 32, 34, 35, 37, 38, 40, 41, 43, 44, 46, 47, 49, 50, 52, 53, 55, 56, 58, 59, 61, 62, 64, 65, 67, 68, 70, 71, 73, 74, 76, 77, 79, 80, 82, 83, 85, 86, 88, 89, 91, 92, 94, 95, 97, 98, 100
sage: %runfile coprimelist.py
12
5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49, 53, 55, 59, 61, 65, 67, 71, 73, 77, 79, 83, 85, 89, 91, 95, 97
sage: %runfile coprimelist.py
9699690
23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
sage: %runfile coprimelist.py
factorial(100)

sage: 

Answer 17

python - 90

Boring answer. The output is a little strange (but meets the rules)

from fractions import *
x=input()
for i in range(2,101):
 if gcd(x,i)==1:print(i,",",end="")

Answer 18

J - 47 char

Requiring input on STDIN (no trailing newlines, please) and outputting to STDOUT in proper form.

(2}.&;(2+i.99)(', ';":)&>@([#~1=+.)".)&.stdin''

2+i.99 is the integers from 2 to 100 inclusive. ([#~1=+.) keeps only those integers coprime to the input, and then (', ';":) converts each (&>) to a string and adds the comma and space before each entry. ; combined the entire result into a single string, and 2}. drops the comma and space before the first one.

Answer 19

ised (28)

ised '@1{6};' '?{{:gcd{x$1}:}@::[101]<2}\1'

The first argument is just setting the argument (6 in this case). The second evaluates the result.

With unicode, it's a bit shorter (26).

ised '@1{6};' '?{{:gcd{x$1}:}∷[101]<2}\1'

Unfortunately, the braces take up a lot of space in ised because it's not stack-based.

Answer 20

wxMaxima: 67 85 80

I had to adjust my answer to fit the specs (i.e., take a value from stdin)

f():=block(n:read(),for i:2thru 100 do if(gcd(i,n)=1)then printf(true,"~d, ",i) )

Call this in the interactive session via f and then enter in your value followed by ctrl+enter to get the result.

---

Old, non-spec fitting answer

f(n):=for i:1thru 100 do(if(gcd(i,n)=1)then printf(true,"~d, ",i));

Enter this into the command line & execute it via f(12); to get

1,5,7,11,13,17,19,23,25,29,31,35,37,41,43,47,49,53,55,59,61,65,67,71,73,77,79,83,85,89,91,95,97,

Answer 21

Python 3 - 79 chars

x=int(input())
for i in range(2,101):print(i) if pow(x,i-1,i)==1or i==x+1else 0

Uses the Fermat primality test to check co-primes.

Answer 22

APL(NARS), 35 chars

5↓∊(⊂', '){⍺⍵}¨' ',⍕¨a⊂⍨1=⎕∨a←1+⍳99

use as:

  5↓∊(⊂', '){⍺⍵}¨' ',⍕¨a⊂⍨1=⎕∨a←1+⍳99
⎕:
  2310
┌78─────────────────────────────────────────────────────────────────────────────┐
│ 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97│
└───────────────────────────────────────────────────────────────────────────────┘

Answer 23

Tcl, 218 bytes

Golfed version. Attempt This Online!

proc gcd {a b} {while {$b} {set t $b; set b [expr {$a % $b}]; set a $t}; return $a}
set n [expr {[gets stdin]}]
set r [list]
for {set k 2} {$k <= 100} {incr k} {if {[gcd $n $k] == 1} {lappend r $k}}
puts [join $r ", "]

Ungolfed version. Attempt This Online!

proc main {} {
    # Read a number from input
    set n [gets stdin]
    
    # Initialize an empty list to store the numbers
    set numbers {}

    # Loop through numbers 2 to 100 and check if gcd with n is less than 2
    for {set k 2} {$k <= 100} {incr k} {
        # Check if the gcd of k and n is 1 (coprime)
        if {[gcd $k $n] < 2} {
            # If so, append k to the list of numbers
            lappend numbers $k
        }
    }
    
    # Join the numbers with a comma and a space, and then print
    puts [join $numbers ", "]
}

proc gcd {a b} {
    # Calculate the greatest common divisor of a and b
    while {$b != 0} {
        set temp $b
        set b [expr {$a % $b}]
        set a $temp
    }
    return $a
}

# Call the main procedure
main