5
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ Why the time limit? Typically challenges on this site do not have a deadline or cutoff. \$\endgroup\$ – Doorknob May 31 '14 at 23:37
  • 2
    \$\begingroup\$ Esoteric languages are now being assessed separately from non-esoteric languages. What does that mean? You can only accept one answer. Is the shortest solution going to win or is it not? \$\endgroup\$ – Dennis Jun 1 '14 at 1:16
  • 10
    \$\begingroup\$ "Esoteric languages (e.g. J or GolfScript) [...]"--hold the phone. Brainfuck is esoteric. Unlambda is esoteric. J is a legitimate array processing language developed in the 90s as a successor to granddaddy APL, often used in research and other data-heavy fields. \$\endgroup\$ – algorithmshark Jun 1 '14 at 2:25
  • 1
    \$\begingroup\$ @algorithmshark OK... what about "terse and unreadable"? \$\endgroup\$ – John Dvorak Jun 1 '14 at 5:01
  • 2
    \$\begingroup\$ -1 for time limit and for language segregation. :-( \$\endgroup\$ – Chris Jester-Young Jun 2 '14 at 14:11

17 Answers 17

6
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ I get people not upvoting solutions in golfing languages, but downvoting them is a bit too much. \$\endgroup\$ – Dennis Jun 2 '14 at 5:42
3
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ What does it do? \$\endgroup\$ – Joe Z. Jun 1 '14 at 0:51
  • 1
    \$\begingroup\$ @JoeZ. I added an explanation \$\endgroup\$ – aditsu Jun 1 '14 at 1:05
  • \$\begingroup\$ My CJam answer is competing with your GolfScript answer. Weird. :P \$\endgroup\$ – Dennis Jun 1 '14 at 1:45
  • \$\begingroup\$ @Dennis I was gonna write it in CJam but I found a bug when trying to join an empty array (will fix in next release). That said, I hadn't thought of using a factorization :) \$\endgroup\$ – aditsu Jun 1 '14 at 2:04
  • \$\begingroup\$ On the other hand, some people seem to hate both languages, we got downvotes :/ \$\endgroup\$ – aditsu Jun 2 '14 at 6:09
3
\$\begingroup\$

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).
\$\endgroup\$
3
\$\begingroup\$

Haskell, 76 characters

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

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}*", "
\$\endgroup\$
  • 1
    \$\begingroup\$ Using a -p option saves you a gets call (the value is read into $_), and a puts (whatever $_ contains at the end is output). \$\endgroup\$ – primo Jun 3 '14 at 5:29
  • 1
    \$\begingroup\$ Interactive mode isn't a caveat, it's a feature ;) (eof character will terminate input (^D linux, ^Z windows), or you can pipe from a file, or echo 9699690 | ruby -p script.rb it in). \$\endgroup\$ – primo Jun 3 '14 at 15:12
1
\$\begingroup\$

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(', ')
\$\endgroup\$
1
\$\begingroup\$

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(', ')
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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: 
\$\endgroup\$
  • \$\begingroup\$ In the last example, it is supposed to print out nothing, but it prints []. \$\endgroup\$ – Alex May 31 '14 at 22:57
  • \$\begingroup\$ Of course it is. \$\endgroup\$ – Alex May 31 '14 at 23:07
  • \$\begingroup\$ No. But your edited code sample fixes that anyway. \$\endgroup\$ – Alex May 31 '14 at 23:23
  • \$\begingroup\$ @Alex I know, but I have a shorter code that does that. \$\endgroup\$ – ace_HongKongIndependence May 31 '14 at 23:24
0
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ 17 char if you make it a train: }.a(]#~1=+.)i.101. \$\endgroup\$ – algorithmshark Jun 1 '14 at 2:43
0
\$\begingroup\$

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="")
\$\endgroup\$
  • \$\begingroup\$ Got this down to 87 bytes (as well as making it actually work), but the changes were pretty significant so I put them in their own answer here. If you want, you can copy those changes over and I'll delete that answer. \$\endgroup\$ – undergroundmonorail Jun 1 '14 at 4:11
  • \$\begingroup\$ Shorten with import* \$\endgroup\$ – Timtech Jun 1 '14 at 14:20
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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. :)

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I haven't been able to find anything about ised anywhere. Could you please give me some background information about it? \$\endgroup\$ – Alex Jun 2 '14 at 0:57
  • 1
    \$\begingroup\$ @Alex It's not very well known but I'm using it as my calculator and data file processor and it's excellent for numerical golfing. ised.sourceforge.net \$\endgroup\$ – orion Jun 2 '14 at 7:22
  • \$\begingroup\$ Also, wouldn't your example be in shell script, not ised, since you're typing it at the terminal? \$\endgroup\$ – Alex Jun 2 '14 at 20:17
  • \$\begingroup\$ @Alex You can enter the same code interactively directly into ised. Two lines. The execution environment is irrelevant. At least from a unix point of view, there's no real difference. You are always in some kind of a terminal anyway just to provide the input file, pipe, stdin, output redirection... you could just as well call this from a c program. \$\endgroup\$ – orion Jun 2 '14 at 20:21
0
\$\begingroup\$

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,
\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Why the down-vote? I did everything required as far as I can tell. \$\endgroup\$ – DavisDude Jun 2 '14 at 19:21
  • 1
    \$\begingroup\$ I didn't cast the downvote, but the solution seems to be invalid. For example, 21 is not evenly divisible by 6, but they aren't co-prime either, as they are both divisible by 3. \$\endgroup\$ – primo Jun 2 '14 at 19:33
  • \$\begingroup\$ Ah. My bad, I will see if I can fix that. \$\endgroup\$ – DavisDude Jun 2 '14 at 19:36
  • \$\begingroup\$ It is fixed, but very long. \$\endgroup\$ – DavisDude Jun 2 '14 at 20:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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