236
\$\begingroup\$

Believe it or not, we do not yet have a code golf challenge for a simple primality test. While it may not be the most interesting challenge, particularly for "usual" languages, it can be nontrivial in many languages.

Rosetta code features lists by language of idiomatic approaches to primality testing, one using the Miller-Rabin test specifically and another using trial division. However, "most idiomatic" often does not coincide with "shortest." In an effort to make Programming Puzzles and Code Golf the go-to site for code golf, this challenge seeks to compile a catalog of the shortest approach in every language, similar to "Hello, World!" and Golf you a quine for great good!.

Furthermore, the capability of implementing a primality test is part of our definition of programming language, so this challenge will also serve as a directory of proven programming languages.

Task

Write a full program that, given a strictly positive integer n as input, determines whether n is prime and prints a truthy or falsy value accordingly.

For the purpose of this challenge, an integer is prime if it has exactly two strictly positive divisors. Note that this excludes 1, who is its only strictly positive divisor.

Your algorithm must be deterministic (i.e., produce the correct output with probability 1) and should, in theory, work for arbitrarily large integers. In practice, you may assume that the input can be stored in your data type, as long as the program works for integers from 1 to 255.

Input

  • If your language is able to read from STDIN, accept command-line arguments or any other alternative form of user input, you can read the integer as its decimal representation, unary representation (using a character of your choice), byte array (big or little endian) or single byte (if this is your languages largest data type).

  • If (and only if) your language is unable to accept any kind of user input, you may hardcode the input in your program.

    In this case, the hardcoded integer must be easily exchangeable. In particular, it may appear only in a single place in the entire program.

    For scoring purposes, submit the program that corresponds to the input 1.

Output

Output has to be written to STDOUT or closest alternative.

If possible, output should consist solely of a truthy or falsy value (or a string representation thereof), optionally followed by a single newline.

The only exception to this rule is constant output of your language's interpreter that cannot be suppressed, such as a greeting, ANSI color codes or indentation.

Additional rules

  • This is not about finding the language with the shortest approach for prime testing, this is about finding the shortest approach in every language. Therefore, no answer will be marked as accepted.

  • Submissions in most languages will be scored in bytes in an appropriate preexisting encoding, usually (but not necessarily) UTF-8.

    The language Piet, for example, will be scored in codels, which is the natural choice for this language.

    Some languages, like Folders, are a bit tricky to score. If in doubt, please ask on Meta.

  • Unlike our usual rules, feel free to use a language (or language version) even if it's newer than this challenge. If anyone wants to abuse this by creating a language where the empty program performs a primality test, then congrats for paving the way for a very boring answer.

    Note that there must be an interpreter so the submission can be tested. It is allowed (and even encouraged) to write this interpreter yourself for a previously unimplemented language.

  • If your language of choice is a trivial variant of another (potentially more popular) language which already has an answer (think BASIC or SQL dialects, Unix shells or trivial Brainfuck derivatives like Headsecks or Unary), consider adding a note to the existing answer that the same or a very similar solution is also the shortest in the other language.

  • Built-in functions for testing primality are allowed. This challenge is meant to catalog the shortest possible solution in each language, so if it's shorter to use a built-in in your language, go for it.

  • Unless they have been overruled earlier, all standard rules apply, including the http://meta.codegolf.stackexchange.com/q/1061.

As a side note, please don't downvote boring (but valid) answers in languages where there is not much to golf; these are still useful to this question as it tries to compile a catalog as complete as possible. However, do primarily upvote answers in languages where the author actually had to put effort into golfing the code.

Catalog

The Stack Snippet at the bottom of this post generates the catalog from the answers a) as a list of shortest solution per language and b) as an overall leaderboard.

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

## Language Name, N bytes

where N is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:

## Ruby, <s>104</s> <s>101</s> 96 bytes

If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the last number in the header:

## Perl, 43 + 2 (-p flag) = 45 bytes

You can also make the language name a link which will then show up in the snippet:

## [><>](http://esolangs.org/wiki/Fish), 121 bytes

<style>body { text-align: left !important} #answer-list { padding: 10px; width: 290px; float: left; } #language-list { padding: 10px; width: 290px; float: left; } table thead { font-weight: bold; } table td { padding: 5px; }</style><script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="language-list"> <h2>Shortest Solution by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr> </thead> <tbody id="languages"> </tbody> </table> </div> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr> </thead> <tbody id="answers"> </tbody> </table> </div> <table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr> </tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr> </tbody> </table><script>var QUESTION_ID = 57617; var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe"; var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk"; var OVERRIDE_USER = 12012; var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page; function answersUrl(index) { return "https://api.stackexchange.com/2.2/questions/" + QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER; } function commentUrl(index, answers) { return "https://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER; } function getAnswers() { jQuery.ajax({ url: answersUrl(answer_page++), method: "get", dataType: "jsonp", crossDomain: true, success: function (data) { answers.push.apply(answers, data.items); answers_hash = []; answer_ids = []; data.items.forEach(function(a) { a.comments = []; var id = +a.share_link.match(/\d+/); answer_ids.push(id); answers_hash[id] = a; }); if (!data.has_more) more_answers = false; comment_page = 1; getComments(); } }); } function getComments() { jQuery.ajax({ url: commentUrl(comment_page++, answer_ids), method: "get", dataType: "jsonp", crossDomain: true, success: function (data) { data.items.forEach(function(c) { if (c.owner.user_id === OVERRIDE_USER) answers_hash[c.post_id].comments.push(c); }); if (data.has_more) getComments(); else if (more_answers) getAnswers(); else process(); } }); } getAnswers(); var SCORE_REG = /<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/; var OVERRIDE_REG = /^Override\s*header:\s*/i; function getAuthorName(a) { return a.owner.display_name; } function process() { var valid = []; answers.forEach(function(a) { var body = a.body; a.comments.forEach(function(c) { if(OVERRIDE_REG.test(c.body)) body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>'; }); var match = body.match(SCORE_REG); if (match) valid.push({ user: getAuthorName(a), size: +match[2], language: match[1], link: a.share_link, }); else console.log(body); }); valid.sort(function (a, b) { var aB = a.size, bB = b.size; return aB - bB }); var languages = {}; var place = 1; var lastSize = null; var lastPlace = 1; valid.forEach(function (a) { if (a.size != lastSize) lastPlace = place; lastSize = a.size; ++place; var answer = jQuery("#answer-template").html(); answer = answer.replace("{{PLACE}}", lastPlace + ".") .replace("{{NAME}}", a.user) .replace("{{LANGUAGE}}", a.language) .replace("{{SIZE}}", a.size) .replace("{{LINK}}", a.link); answer = jQuery(answer); jQuery("#answers").append(answer); var lang = a.language; lang = jQuery('<a>'+lang+'</a>').text(); languages[lang] = languages[lang] || {lang: a.language, lang_raw: lang.toLowerCase(), user: a.user, size: a.size, link: a.link}; }); var langs = []; for (var lang in languages) if (languages.hasOwnProperty(lang)) langs.push(languages[lang]); langs.sort(function (a, b) { if (a.lang_raw > b.lang_raw) return 1; if (a.lang_raw < b.lang_raw) return -1; return 0; }); for (var i = 0; i < langs.length; ++i) { var language = jQuery("#language-template").html(); var lang = langs[i]; language = language.replace("{{LANGUAGE}}", lang.lang) .replace("{{NAME}}", lang.user) .replace("{{SIZE}}", lang.size) .replace("{{LINK}}", lang.link); language = jQuery(language); jQuery("#languages").append(language); } }</script>

\$\endgroup\$
8
  • 2
    \$\begingroup\$ Is there a reason for the full program requirement, rather than allowing the full range of default input types? E.g. answering with a function that takes its input as an argument, is currently disallowed? codegolf.meta.stackexchange.com/questions/2447/… \$\endgroup\$ Commented Dec 12, 2017 at 6:21
  • 2
    \$\begingroup\$ @LyndonWhite This was intended as a catalog (like “Hello, World!”) of primality tests, so a unified submission format seemed preferable. It's one of two decisions about this challenge that I regret, the other being only allowing deterministic primality tests. \$\endgroup\$
    – Dennis
    Commented Dec 12, 2017 at 12:51
  • 1
    \$\begingroup\$ Could a case be made for locking this challenge and posting a new, less restrictive one? \$\endgroup\$
    – Shaggy
    Commented Jun 25, 2018 at 12:59
  • 2
    \$\begingroup\$ @Shaggy Seems like a question for meta. \$\endgroup\$
    – Dennis
    Commented Jun 25, 2018 at 13:44
  • 1
    \$\begingroup\$ Yeah, that's what I was thinking. I'll let you do the honours, seeing as it's your challenge. \$\endgroup\$
    – Shaggy
    Commented Jun 25, 2018 at 13:45

369 Answers 369

1 2 3
4
5
13
4
\$\begingroup\$

Logicode, 601 511 467 bytes

circ o(n)->cond n<->0+n/o(n>)
circ p(n)->[
cond n->var c=~((~(o(n)))>)/var c=0
cond (~n)<->var d=p(c)+0/var d=c+1
d
]
circ q(n)->[
cond n->var e=~((~(o(n)))>)/var e=0
cond (~n)<->var f=e+0/var f=q(e)+1
f
]
circ r(a,b)->cond *a&*b->r(q(a),q(b))/a
circ s(a,b)->!(*(r(b,a)))
circ t(a,b)->cond b->t(q(a),q(b))/a
circ u(a,b)->cond s(a,b)->u(t(a,b),b)/!(*a)
circ v(a)->[
var j=p(j)
cond s(a,j)->[
var k=k+u(a,j)
var l=v(a)
]/[
var k=k
]
*((~k)>)
]
var j=1
var k
out v(binp)

Oh my, that is a lot of code.

Here's a rundown of what each circuit does:

  • o is a trimmer, and it strips the extra 0's at the start (this is used for p and q.
  • p is a successor, and q is a decrement.
  • r is a preliminary bit to s (lessthan).
  • s is the lessthan (which uses the remainder checker).
  • t is a subtractor, which calculates a - b for any two positive integers a and b (in binary).
  • u is a mod checker, which returns 1 if a%b is not 0, and 0 if it is 0.
  • v is the actual prime checker, which returns 1 if the number is not prime, and 0 if the number is.
    • The j and k at the bottom are the divisor (b in the mod checker) and the un-bool'd output respectively.

The final line is the "input" bit, which asks for user input in binary (any other character that is not 0 or 1 in the input will be ignored), and returns 1 if the result is not prime, and 0 if the result is.

Edit 1: Saved a whopping 90 bytes (implemented circ/cond one-liners).

Edit 2: Saved another 44 bytes (implemented boolean operator, multi-line conds, and null variables).

\$\endgroup\$
4
\$\begingroup\$

Dyalog APL, 10 9 bytes

2=∘≢∘∪⍳∨⊢

I don't think this one has been posted.

\$\endgroup\$
4
\$\begingroup\$

Tcl, 78 75 bytes

Thanks to sergiol

if $argv<2 {exit 1}
incr d
while {[incr d]<$argv} {if $argv%$d==0 {exit 1}}

Original version

if {$argv<2} {exit 1}
incr d
while {[incr d]<$argv} {if {$argv%$d==0} {exit 1}}

Works for all integer values (both negative and arbitrarily large). However, as this aims to be short and not efficient, it is written with a simple divisor={2,3,4,...} loop, so you'll begin getting noticeable lag around eight digit numbers (n ≥ 108).

The input is taken on the command-line; the output is an exit code: 0 for prime and 1 for not prime.

On Windows you can use the following batch file to test it:

@echo off
tclsh a.tcl %1
if ERRORLEVEL 1 (
  echo not prime
) else (
  echo prime
)

Use it as:

C:\foo> run.bat 2017
prime

On *nixen you can use the following bash script to test it:

#! /bin/sh
tclsh a.tcl $1
if [ $? -eq 0 ]
then
  echo prime
else
  echo not prime
fi

Use it as:

% ./run.sh 2017
prime

Enjoy!

\$\endgroup\$
4
  • \$\begingroup\$ You can save some bytes: tio.run/##K0nO@f8/… \$\endgroup\$
    – sergiol
    Commented Oct 23, 2017 at 0:40
  • \$\begingroup\$ Please be careful to test stuff before suggesting edits. ! has higher precedence than %, so the ==0 remains... Other edits made from your suggestion. Thanks! \$\endgroup\$
    – Dúthomhas
    Commented Oct 23, 2017 at 1:49
  • \$\begingroup\$ I tested it on my local machine and it seemed to work \$\endgroup\$
    – sergiol
    Commented Oct 23, 2017 at 9:18
  • \$\begingroup\$ Nobody else is testing the validity of the inputs, so you can remove the 1. line. \$\endgroup\$
    – sergiol
    Commented Nov 18, 2023 at 19:41
4
\$\begingroup\$

Symbolic Python, 48 bytes

___=_
__("__=_/_"+";_=-~_;__*=_*_"*~-_)
_=__%___

Try it online!

Uses Wilson's theorem, i.e. that \$(n-1)!^{2} \% n = 1\$ if \$n\$ is a prime, otherwise it equals \$0\$.

Explanation:

___=_                              # Save the value of input to ___
__(                             )  # Evaluate string
   "__=_/_"                        # Initialise __ as 1
           +";             "*~-_   # Then repeat n-1 times
              _=-~_;               # Decrement n
                    __*=_*_        # Multiply __ by n squared
_=__%___                           # Output the value of __ modulo ___
\$\endgroup\$
4
\$\begingroup\$

Alchemist, 126 bytes

_->In_a
a->b+c
0e+b+c->g+h
f+0c+b->e+b
e+0h+c->f+c
f+0b+c->c
0e+0f+g->b
0f+h+0s->c
0f+0a+0g+0h+c->f
f+0b+0c+h->s
s+0h->Out_"1"

Try it online!

Outputs 1 for primes, and nothing for composite numbers. Here's a script that tests the program against numbers below 100.

This is rather inefficient, as I removed a restriction that prevented one rule undoing another rule for a sweet one byte save (worth it!). To be much more efficient, we can replace the 0e in the third rule with f and add f to the other side too. Try it online!

Explanation:

_->In_a           # Create the input number of a atoms
a->b+c            # Convert all them to b and c atoms
                  # b will serve as a permanent save of the input
                  # c will be a counter starting at the input

0f+0a+0g+0h+c->f  # Decrement c and start the main loop by setting the f flag
# Note that f and 0e are mostly interchangeable, and the same with 0f and e     
0e+b+c->g+h       # Subtract the counter from the input, keeping a copy of both
f+0c+b->e+b       # When the counter runs out, set the e flag
0f+h+0s->c        # Move the temporary counter atoms back to the main counter
e+0h+c->f+c       # Once done, set the f flag again
f+0b+c->c         # If the counter isn't 0 when the input reaches 0
                  # Then the input is not divisible by the counter

0e+0f+g->b        # Convert the temporary input atoms back to the main input
                  # Reuse the temp counter to main counter rule again

# Once both are done, start the loop over again, decrementing the counter
# This continues until:

f+0b+0c+h->s      # If both the counter and the input reach 0 at the same time
                  # Then the input is currently divisible by the counter
                  # Decrement the temporary counter atom
s+0h->Out_"1"     # If the temp counter is 0 after that (i.e. the highest factor is 1)
                  # Print 1
\$\endgroup\$
4
\$\begingroup\$

Java, 108 bytes

interface P{static void main(String[]a){long l=new Long(a[0]),i=1;for(;0<l%++i%l;);System.out.print(l==i);}}

Try it online!

Port of my Ink answer. Would beat all existing answers in C#, Python (2 and 3), and possibly other languages if ported.

Ungolfed

interface PrimeChecker {
    // Unlike members of classes, members of interfaces are public by default. 
    static void main(String[] args) {
        long input = new Long(args[0]),
             div = 1;
        for (; 0 < (  input % (++div) // Trial division, finish when div divides input
                    % input           /* If input is at least 2, this has no effect.
                                         But (1 % n) = 1 for any n > 1
                                         so without this, the loop would never end
                                         when the input is 1 */
                   );
            ) { /* The loop body is empty, we're just using it to set div */ }
        // div is now the lowest number greater than 1 that divides the input
        // (or 2, if the input is 1)

        // The input is prime iff that number is equal to the input
        System.out.println(input == div);
    }
}
\$\endgroup\$
1
  • \$\begingroup\$ Note for those who, like me, didn't understand the existence of the last %l at first, it's to shortcut the loop when the input is 1. \$\endgroup\$ Commented May 16, 2019 at 15:42
4
\$\begingroup\$

Taxi, 1238 bytes

Go to Post Office:w 1 l 1 r 1 l.Pickup a passenger going to The Babelfishery.Go to The Babelfishery:s 1 l 1 r.Pickup a passenger going to Cyclone.Go to Cyclone:n 1 l 1 l 2 r.Pickup a passenger going to Cyclone.Pickup a passenger going to The Underground.Go to The Underground:n 2 r 2 r.Switch to plan q i.[l]Pickup a passenger going to Cyclone.Go to Zoom Zoom:n 3 l 2 r.Go to Cyclone:w.Pickup a passenger going to Divide and Conquer.Pickup a passenger going to Sunny Skies Park.Pickup a passenger going to Divide and Conquer.Go to Sunny Skies Park:n 1 r.Go to Divide and Conquer:n 1 r 1 r 2 r 1 r.Pickup a passenger going to Cyclone.Go to Cyclone:e 1 l 1 l 2 l.Pickup a passenger going to The Underground.Pickup a passenger going to Equal's Corner.Pickup a passenger going to Trunkers.Go to Trunkers:s 1 l.Pickup a passenger going to Equal's Corner.Go to Equal's Corner:w 1 l.Switch to plan c i.Go to The Underground:n 3 r 1 r 2 l.Switch to plan p i.[q]0 is waiting at Writer's Depot.[p]1 is waiting at Writer's Depot.Go to Writer's Depot:n 3 l 2 l.Pickup a passenger going to Post Office.Go to Post Office:n 1 r 2 r 1 l.[c]Go to Sunny Skies Park:n.Pickup a passenger going to Cyclone.Go to The Underground:n 1 r 1 r 2 r.Switch to plan l.

Try it online!


With many ideas from this answer, but 1 character shorter using the same shortening techniques.note This takes a slightly different approach so that “The Underground” is the return point for each iteration instead of “Zoom Zoom”. Even though this ends up only 1 character shorter, it's actually one whole instruction shorter! The reduction is relatively little because there's 2 more turns and “The Underground” is mentioned more.

The ways this answer has golfed more than the linked answer are as follows:

  • Removing all quotes around plans and strings. As long as there is no space or other special character they are not needed.
  • For the Switch to plan "name" if no one is waiting the only check is whether there is any text after "name". This means that the if no one is waiting part can be replaced with i.
  • If we did use quotes like the original answer we could also remove the spaces after closing quotes.

This is the code ungolfed with some comments.

    [Read number and convert to int]
Go to Post Office: west 1st left, 1st right, 1st left.
Pickup a passenger going to The Babelfishery.
Go to The Babelfishery: south 1st left, 1st right.

    [Duplicate to get numerator and denominator]
Pickup a passenger going to Cyclone.
Go to Cyclone: north 1st left, 1st left, 2nd right.

    [Decrement denominator and duplicate both]
Pickup a passenger going to Cyclone.
Pickup a passenger going to The Underground.
Go to The Underground: north 2nd right, 2nd right.
Switch to plan "not prime" if no one is waiting.
[loop]
Pickup a passenger going to Cyclone.
Go to Zoom Zoom: north 3rd left, 2nd right.
Go to Cyclone: west.

    [Pickup for division...]
Pickup a passenger going to Divide and Conquer.
Pickup a passenger going to Sunny Skies Park.
Pickup a passenger going to Divide and Conquer.
Go to Sunny Skies Park: north 1st right.
Go to Divide and Conquer: north 1st right, 1st right, 2nd right, 1st right.
Pickup a passenger going to Cyclone.
Go to Cyclone: east 1st left, 1st left, 2nd left.

    [Copy result to check if integer, first pickup ]
Pickup a passenger going to The Underground.
Pickup a passenger going to Equal's Corner.
Pickup a passenger going to Trunkers.
Go to Trunkers: south 1st left.
Pickup a passenger going to Equal's Corner.

    [Check if integer]
Go to Equal's Corner: west 1st left.
Switch to plan "continue" if no one is waiting.
Go to The Underground: north 3rd right, 1st right, 2nd left.
Switch to plan "prime" if no one is waiting.

    [Print whether it's a prime or not]
[not prime]
0 is waiting at the Writer's Depot.
[prime]
1 is waiting at the Writer's Depot.
Go to Writer's Depot: north 3rd left, 2nd left.
Pickup a passenger going to Post Office.
Go to Post Office: north 1st right, 2nd right, 1st left.

    [Pickup numerator and decrement denominator for checking lower numbers]
[continue]
Go to Sunny Skies Park: north.
Pickup a passenger going to Cyclone.
Go to The Underground: north 1st right, 1st right, 2nd right.
Switch to plan "loop".

Try it online!

\$\endgroup\$
4
\$\begingroup\$

Vyxal, 3 bytes

KḢ₃

Try it Online!

I thought something non trivial would be nice for a change. æ does the job for one byte but where's the fun in that?

-1 thanks to EmanresuA

Explained

KḢ₃
KḢ   # factors(input)[1:]
  ₃  # len(^) == 1 // prime numbers have only [1, n] as factors...other numbers have 1 or 3+ factors
\$\endgroup\$
2
  • \$\begingroup\$ This can be KḢ₃ \$\endgroup\$
    – emanresu A
    Commented Nov 1, 2021 at 8:57
  • \$\begingroup\$ Also, 5 bytes version with no factorisation - 4 with r if you remove the $ \$\endgroup\$
    – emanresu A
    Commented Nov 1, 2021 at 9:03
4
\$\begingroup\$

<>^v, 184 bytes

Prints 1 if number is prime, otherwise 0.

>]v2i>IT%0=vIT[vv
             > vv
1          I   TI
T          T    )
T          =    i
t          > ^  v
,    ^          <
               v
               >"1";
  >        >"0";
^@|

Explanation

@  Pointer starts here, goes right
|  Mirror — reverse pointer direction
@  No-op because the program is already running
^  Send instruction pointer up
,  Read number from stdin and push to stack
t  Pop and store in variable `t`
T  Push value of variable `t`
T  Same
1  Push 1
>  Send instruction pointer right
]  If top element of stack is greater or equal to the second element of the stack
  v  Send instruction pointer down
  >  Send instruction pointer right
  Go to [not prime]
Else
2  Push 2
i  Pop and store into variable `i`
[loop start]
>  Send instruction pointer right
I  Push value of variable `i`
T  Push value of variable `t`
%  Set top of stack to top of stack modulo second element of stack
0  Push 0
=  If the top two elements of the stack are equal
  v  Send instruction pointer down
  I  Push value of variable `i`
  T  Push value of variable `t`
  =  If the top two elements of the stack are equal
    >  Send instruction pointer right
    ^  Send instruction pointer up
    >  Send instruction pointer right
    Go to [prime]
  Else
[not prime]
    >  Send instruction pointer right
    "0"  Push "0"
    ;  Print top of stack
    ';' was the last character of this row, program exits
Else
I  Push value of variable `i`
T  Push value of variable `t`
If the first element of the stack (t) is smaller or equal to the second element of the stack (i)
  v  Send instruction pointer down
[prime]
  v  Send instruction pointer down
  T  Push value of T
  v  Send instruction pointer down (there only to ensure the row is long enough)
  >  Send instruction pointer right
  "1"  Push "1"
  ;  Print top of stack
  Since ';' was the last character of the row, exit
v  Send instruction pointer down
v  Idem
I  Push value of variable `i`
)  Increment top of stack
i  Pop stack and store in variable `i`
v  Send instruction pointer down
<  Send instruction pointer left
^  Send instruction pointer up
Go to [loop start]

More simply, it first checks if the number is lower or equal to 1. If so, it prints 0 and exits. Then, it sets the variable i (current divisor) to 2. Then the program enters a loop. In that loop:

  • If the number modulo i is 0:
    • If i == number, print 1 and exit (prime). Else, print 0 and exit (has found a divisor, number isn't prime).
  • Then it increments i, and goes back to the beginning of the loop.

run online

\$\endgroup\$
4
\$\begingroup\$

Google Sheets, 29 bytes

=mod(fact(A1-1),A1)=mod(-1,A1

Try it on my Google Sheet It uses Wilson’s theorem, which, in modular arithmetic, is:

(n − 1)! ≡ −1 (mod n) 

read: n − 1 factorial is congruent modulo n to negative 1

However, it is important to maintain the distinction between (mod n) notation and and the modulo operator. We could rewrite Wilson’s theorem using more familiar mod operators:

(n − 1)! % n = -1 % n

and that’s what i wrote into google sheets. Google Sheets also does parenthesis autocompletion, so i omitted the final parentheses.

\$\endgroup\$
4
\$\begingroup\$

Trilangle 1.3, 31 29 bytes

<'?<#2%._zS<.>(>.,)2-/\\_/!@@

Reads a single integer from STDIN, and prints 0 iff it's prime.

Try it on the online interpreter!

TL;DR

Keeps a running counter that starts at 2, and increments it until (input % counter) == 0. Then, it prints '0' if input == counter.

What is Trilangle?

Trilangle is a 2-D stack-based programming language. Program flow can be redirected with "mirrors" /|\_ or with branches <^7>vL. The branches can split, merge, or reflect control flow, depending on how they're used. If the IP walks off the board, it continues one row or diagonal to its left.

Code Explanation

Unfolds to this example from the README:

       <
      ' ?
     < # 2
    % . _ z
   S < . > (
  > . , ) 2 -
 / \ \ _ / ! @
@ . . . . . . .

Equivalent to this C code:

#include <stdio.h>

// Get an integer from stdin. Implementation provided by the interpreter.
extern int getint(void);

int main() {
  // RED PATH
  int input = getint();
  int counter = 2;
  while (input % counter)
    // GREEN PATH
    ++n;
  // BLUE PATH
  if (input == counter)
    // YELLOW PATH
    return 0;
  // MAGENTA PATH
  puts("0");
  return 0;
}

This uses the new 2DUP instruction z to make stack management easier: it copies both the input and counter so that they may be operated on non-destructively. The older version below used a combination of j (indexed read), 2 (duplicate), and S (swap) to achieve a similar effect.

Older answer: Trilangle 1.0,  42  41 40 bytes

'2.?..<[email protected]'2,<|>(%!.\S)S,,)S<.....@>-
\$\endgroup\$
3
\$\begingroup\$

Ruby, 16 + 6 = 22 bytes

[*$<];p$..prime?

or equivalently

p$<.count.prime?

Rules abuse! Kind of, anyway. This answer requires that the input be in unary, and that the character used for input be a newline. Invoke like

ruby -rprime prime_test.rb input

Where input is a file containing n newlines.

I calculate this at 22 bytes: 6 for "rprime" and 16 for the code. However, I also calculate manatwork's answer at 22 bytes if you golf the command line invocation (7 for 'nrprime' and 15 for the code).

\$\endgroup\$
2
  • \$\begingroup\$ Are you sure that Ruby's prime? doesn't use a probabilistic test? \$\endgroup\$ Commented Sep 14, 2015 at 10:23
  • 1
    \$\begingroup\$ Yes, it loops through a pseudoprime generator (which returns a superset of the primes) and checks for divisibility of each number less than it. \$\endgroup\$
    – histocrat
    Commented Sep 14, 2015 at 12:07
3
\$\begingroup\$

Ruby, 21 + 1 = 22 19 + 1 = 20 bytes

Also throwing my hat into the Ruby battle using the regex approach (and improved using histocrat's suggestion):

p !/^(11+)\1+$|^1$/

Takes input as a unary string and invoked using the n flag:

$ ruby -ne 'p !/^(11+)\1+$|^1$/' <<< 11111
true
\$\endgroup\$
3
  • \$\begingroup\$ Ooh, you can drop two in fact. p !/^(11+)\1+$|^1$/ \$\endgroup\$
    – histocrat
    Commented Sep 11, 2015 at 18:25
  • \$\begingroup\$ @histocrat Interesting. I didn't know about that. However, it gives me warning: regex literal in condition. Since the rules state "if possible, output should consist solely of the string representation of a truthy or falsy value," I'd need to add the W0 flag, so it's a wash. Thanks for the tip, though. \$\endgroup\$ Commented Sep 11, 2015 at 18:52
  • \$\begingroup\$ @histocrat A-ha, it only gives that warning when I run it from a file rather than as a one-liner. So thank you indeed for that. \$\endgroup\$ Commented Sep 11, 2015 at 20:45
3
\$\begingroup\$

O, 23 bytes

j.1>\J2/{Jn%0={0}{}?}dp

Take 2! This one uses trial by division.

\$\endgroup\$
3
\$\begingroup\$

Python 2, 46 65 52 51 bytes

  1. Went up to 65 bytes - Fix made thanks to feersum & Mauris
  2. Went down to 52 bytes - Suggestions made by kirbyfan64sos and accepts in input from STDIN to complete the code.
  3. Went down to 51 bytes - Suggestion made by kirbyfan64sos (thanks again!) to remove the space between 1 and and. Apparently if you have a letter that follows a number, a space isn't needed... how weird, but cool!

This finds the remainder / modulus of the input integer n divided by every number from 2 up to n-1. If there is at least one number in this sequence that has no remainder, or results in 0, this means that the number is not prime. If every value in this sequence is non-zero, the value is prime. Also by definition, 1 isn't prime and so that has to be taken care of separately.

n=input();print n!=1and all(n%i for i in range(2,n))

Example Runs

I ran this in IPython:

In [10]: n=input();print n!=1and all(n%i for i in range(2,n))
1
False

In [11]: n=input();print n!=1and all(n%i for i in range(2,n))
2
True

In [12]: n=input();print n!=1and all(n%i for i in range(2,n))
3
True

In [13]: n=input();print n!=1and all(n%i for i in range(2,n))
4
False

In [14]: n=input();print n!=1and all(n%i for i in range(2,n))
5
True

In [15]: n=input();print n!=1and all(n%i for i in range(2,n))
6
False

In [16]: n=input();print n!=1and all(n%i for i in range(2,n))
7
True

In [17]: n=input();print n!=1and all(n%i for i in range(2,n))
10
False

In [18]: n=input();print n!=1and all(n%i for i in range(2,n))
15
False

In [19]: n=input();print n!=1and all(n%i for i in range(2,n))
17
True

In [20]: n=input();print n!=1and all(n%i for i in range(2,n))
20
False

In [21]: n=input();print n!=1and all(n%i for i in range(2,n))
30
False
\$\endgroup\$
15
  • \$\begingroup\$ It has to return false for 1. \$\endgroup\$
    – feersum
    Commented Sep 12, 2015 at 0:40
  • \$\begingroup\$ You made it return False for every possible input but 1, which should be False :) \$\endgroup\$
    – lynn
    Commented Sep 12, 2015 at 1:05
  • \$\begingroup\$ @Mauris - Oops. I didn't fix that properly lol. Was on mobile. I'm on my computer now. Fixing. \$\endgroup\$
    – rayryeng
    Commented Sep 12, 2015 at 1:07
  • \$\begingroup\$ @Mauris - Fixed now. Thanks. \$\endgroup\$
    – rayryeng
    Commented Sep 12, 2015 at 1:12
  • 1
    \$\begingroup\$ Wow, this is almost the exact same code I wrote :) You can save a char by using > instead of !=. \$\endgroup\$
    – J Atkin
    Commented Sep 21, 2015 at 15:14
3
\$\begingroup\$

C, 61 bytes

r;main(i,j){r=(--i>1);for(j=i-1;j>1;)r*=!!(i%j--);return r;}

Uses unary representation - the number is encoded in the number of commandline arguments. The return value is initialized to 1 and then, it's multiplied by the sign of remainder of division of the tested number and numbers 2..i-1 in a loop. So it will be zeroed when any non-trivial divisor found.

The result is returned to the system as the exit code.

Test:

echo 'r;main(i,j){r=(--i>1);for(j=i-1;j>1;)r*=!!(i%j--);return r;}' > main.c
gcc -o main main.c
./main 1 ; echo $?
./main 1 1 ; echo $?
./main 1 1 1 ; echo $?
./main 1 1 1 1 ; echo $?
./main 1 1 1 1 1 ; echo $?
./main 1 1 1 1 1 1 ; echo $?
./main 1 1 1 1 1 1 1 ; echo $?
./main 1 1 1 1 1 1 1 1 ; echo $?
./main 1 1 1 1 1 1 1 1 1 ; echo $?
./main 1 1 1 1 1 1 1 1 1 1 ; echo $?
./main 1 1 1 1 1 1 1 1 1 1 1 ; echo $?
\$\endgroup\$
3
\$\begingroup\$

Bash+coreutils, 29 bytes

echo $[`factor $1|wc -w`==2]

Test:

echo 'echo $[`factor $1|wc -w`==2]' > primetest.sh
chmod +x primetest.sh
./primetest.sh <NUMBER_TO_TEST>
\$\endgroup\$
3
\$\begingroup\$

Fortran 90, 66 55 bytes

Using trial division.

read*,i
do1 j=2,i
1 if(mod(i,j)==0)exit
print*,i==j
end

Saved 11 bytes thanks to sigma.

A do loop with labelled statement (not an enddo or continue) is still valid in Fortran 90, but obsolete.

Alternative using Wilson's theorem (56 bytes):

read*,j
k=1
do1 i=2,j-1
1 k=mod(k*i,j)
print*,k==j-1
end
\$\endgroup\$
1
  • \$\begingroup\$ Aww you beat me, now I'll have to come up with a different Fortran solution! Some tips though: the program statement is not necessary, which will save you 9 bytes, and you can also get away with writing do1 instead of do 1. \$\endgroup\$
    – sigma
    Commented Sep 13, 2015 at 20:43
3
\$\begingroup\$

Smalltalk, 47 characters

Obviously no competition for isPrime if the Smalltalk dialect has it, but not all do. For example, the one used in Coding Ground (GNU Smalltalk v3.2.5) does not have it.

I'm relying on the observation that GCD((n - 1)!, n) = 1 for prime n which I haven't seen used very often. Ridiculously bad algorithm, but Smalltalk has no problem working with large integers. Replace the 2 with whatever you want to test:

|n|n:=2.((n>1)&((n-1)factorial gcd:n)=1)inspect

It does not consider 1 as prime as required by the OP. However, one widely accepted definition of a prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. So by this definition, 1 shouldn't be a candidate for primality testing, any more than 0, ½, i, e or π should be.

Note that in some situations, -1 is considered prime, because -1 = 1 × -1, and is used as such in some factorization algorithms.

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

J, 4 bytes

1&p:

This is essentially a built-in function for J as p: provides several different prime-related functions, depending on the left argument (attached here with 1&).

As with J in general, it is incredibly array-friendly:

   1&p: 0 1 2 3 4 5 6 7 8 9 10
0 0 1 1 0 1 0 1 0 0 0
\$\endgroup\$
3
\$\begingroup\$

C#, 156 133 130 bytes

(second attempt after the first didn't exactly work)

using System;class C{static void Main(string[]a){int i=2,n=int.Parse(a[0]),b=n-1;for(;i<=n/2;)b*=n%i++>0?1:0;Console.Write(b>0);}}

(and thanks to Dennis for helping me out with my first code golf :) )

\$\endgroup\$
6
  • 1
    \$\begingroup\$ Welcome to Programming Puzzles & Code Golf! In its current form, your answer simply prints the result of the last divisibility test. You can fix that by initializing b=1 and multiplying b by the results (b*=...). \$\endgroup\$
    – Dennis
    Commented Sep 15, 2015 at 16:05
  • \$\begingroup\$ I'm not a C# expert, but since C# doesn't have implicit int-to-bool conversion, I don't think 1/0 satisfy the definition of truthy/falsy. using System;class C{static void Main(string[] a){int i=2,n=Int32.Parse(a[0]),b=n-1;for(;i<=n/2;)b*=n%i++>0?1:0;Console.Write(b>0);}} produces the proper output (and is 23 bytes shorter). \$\endgroup\$
    – Dennis
    Commented Sep 15, 2015 at 16:14
  • \$\begingroup\$ Ah, I see. I would have said that 1/0 does satisfy the condition, but I'll stick with your definition. :) \$\endgroup\$
    – helencrump
    Commented Sep 15, 2015 at 16:16
  • 2
    \$\begingroup\$ For most languages, it does. However, our definition counts 1 as truthy if if(1){...} executes the block, which doesn't seem to wok in C# (again, not an expert). \$\endgroup\$
    – Dennis
    Commented Sep 15, 2015 at 16:20
  • 1
    \$\begingroup\$ You can remove the space between string[] and a. Also, you can change Int32 to just int. \$\endgroup\$ Commented Sep 19, 2015 at 15:53
3
\$\begingroup\$

Perl, 25 bytes

#!perl -p
$_=2==grep$'%$_<1,//..$_

Counting the shebang as one. Input is taken, in decimal, from stdin.

Sample Usage:

$ echo 101101 | perl isprime.pl

$ echo 101107 | perl isprime.pl
1

Perl, 24 bytes

#!perl -p
$_=3>grep$'%$_<1,//..$_

One byte can be shaved by replacing 2== with 3>, however, it will incorrectly identify both 0 and 1 as prime.

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

Ouroboros, 39 bytes

Sr0s1(
)S1+.@@.@@%!Ms+S.@@.@>6*(6s2=n1(

Each line of code in an Ouroboros program represents a snake eating its tail.

Snake 1

S switches to the shared stack; r0 reads a number from input and pushes a 0. Then s1( switches back to snake 1's stack, pushes a 1, and eats that many characters of the tail. The instruction pointer is on a character that gets eaten, so the snake dies.

Snake 2

Here the magic happens. We check every number from 1 up through n, adding 1 to a tally if it divides our input number. At the end we check whether the number of factors equals 2 and print 1 or 0 accordingly.

) is a no-op the first time through. S switches to the shared stack. We then push a 1 (just after the first snake pushes its 0) and add. The stack now contains the input number and the factor we're testing for divisibility.

.@@.@@%! makes copies of both numbers, takes the modulus, and negates (1 if it is a factor, 0 if not). M moves that result to snake 2's stack, where we're storing the tally of factors; then s+S switches to that stack, adds the top two numbers, and switches back to the shared stack.

Next, .@@.@>6* makes copies of both numbers and tests whether the input number is greater than the test factor, pushing 6 if so and 0 if not. ( then eats that many characters from the end of the snake.

  • If the number is still greater than the factor, the uneaten code now ends after (6. This pushes a 6 and wraps execution back to the beginning. There ) regurgitates the 6 characters we just ate. S does nothing because we're already on the shared stack. 1+ then increments the test factor, and we go through the loop again.
  • When the number is no longer greater than the factor, nothing gets eaten and execution continues. We push a 6 but then switch to snake 2's stack, where the number of factors is sitting. 2=n tests whether it's 2 and outputs the result (1 or 0) as a number. Finally, 1( eats the last character and dies.

Try it out

// Define Stack class
function Stack() {
  this.stack = [];
  this.length = 0;
}
Stack.prototype.push = function(item) {
  this.stack.push(item);
  this.length++;
}
Stack.prototype.pop = function() {
  var result = 0;
  if (this.length > 0) {
    result = this.stack.pop();
    this.length--;
  }
  return result;
}
Stack.prototype.top = function() {
  var result = 0;
  if (this.length > 0) {
    result = this.stack[this.length - 1];
  }
  return result;
}
Stack.prototype.toString = function() {
  return "" + this.stack;
}

// Define Snake class
function Snake(code) {
  this.code = code;
  this.length = this.code.length;
  this.ip = 0;
  this.ownStack = new Stack();
  this.currStack = this.ownStack;
  this.alive = true;
  this.wait = 0;
  this.partialString = this.partialNumber = null;
}
Snake.prototype.step = function() {
  if (!this.alive) {
    return null;
  }
  if (this.wait > 0) {
    this.wait--;
    return null;
  }
  var instruction = this.code.charAt(this.ip);
  var output = null;
  console.log("Executing instruction " + instruction);
  if (this.partialString !== null) {
    // We're in the middle of a double-quoted string
    if (instruction == '"') {
      // Close the string and push its character codes in reverse order
      for (var i = this.partialString.length - 1; i >= 0; i--) {
        this.currStack.push(this.partialString.charCodeAt(i));
      }
      this.partialString = null;
    } else {
      this.partialString += instruction;
    }
  } else if (instruction == '"') {
    this.partialString = "";
  } else if ("0" <= instruction && instruction <= "9") {
    if (this.partialNumber !== null) {
      this.partialNumber = this.partialNumber + instruction;  // NB: concatenation!
    } else {
      this.partialNumber = instruction;
    }
    next = this.code.charAt((this.ip + 1) % this.length);
    if (next < "0" || "9" < next) {
      // Next instruction is non-numeric, so end number and push it
      this.currStack.push(+this.partialNumber);
      this.partialNumber = null;
    }
  } else if ("a" <= instruction && instruction <= "f") {
    // a-f push numbers 10 through 15
    var value = instruction.charCodeAt(0) - 87;
    this.currStack.push(value);
  } else if (instruction == "$") {
    // Toggle the current stack
    if (this.currStack === this.ownStack) {
      this.currStack = this.program.sharedStack;
    } else {
      this.currStack = this.ownStack;
    }
  } else if (instruction == "s") {
    this.currStack = this.ownStack;
  } else if (instruction == "S") {
    this.currStack = this.program.sharedStack;
  } else if (instruction == "l") {
    this.currStack.push(this.ownStack.length);
  } else if (instruction == "L") {
    this.currStack.push(this.program.sharedStack.length);
  } else if (instruction == ".") {
    var item = this.currStack.pop();
    this.currStack.push(item);
    this.currStack.push(item);
  } else if (instruction == "m") {
    var item = this.ownStack.pop();
    this.program.sharedStack.push(item);
  } else if (instruction == "M") {
    var item = this.program.sharedStack.pop();
    this.ownStack.push(item);
  } else if (instruction == "y") {
    var item = this.ownStack.top();
    this.program.sharedStack.push(item);
  } else if (instruction == "Y") {
    var item = this.program.sharedStack.top();
    this.ownStack.push(item);
  } else if (instruction == "\\") {
    var top = this.currStack.pop();
    var next = this.currStack.pop()
    this.currStack.push(top);
    this.currStack.push(next);
  } else if (instruction == "@") {
    var c = this.currStack.pop();
    var b = this.currStack.pop();
    var a = this.currStack.pop();
    this.currStack.push(c);
    this.currStack.push(a);
    this.currStack.push(b);
  } else if (instruction == ";") {
    this.currStack.pop();
  } else if (instruction == "+") {
    var b = this.currStack.pop();
    var a = this.currStack.pop();
    this.currStack.push(a + b);
  } else if (instruction == "-") {
    var b = this.currStack.pop();
    var a = this.currStack.pop();
    this.currStack.push(a - b);
  } else if (instruction == "*") {
    var b = this.currStack.pop();
    var a = this.currStack.pop();
    this.currStack.push(a * b);
  } else if (instruction == "/") {
    var b = this.currStack.pop();
    var a = this.currStack.pop();
    this.currStack.push(a / b);
  } else if (instruction == "%") {
    var b = this.currStack.pop();
    var a = this.currStack.pop();
    this.currStack.push(a % b);
  } else if (instruction == "_") {
    this.currStack.push(-this.currStack.pop());
  } else if (instruction == "I") {
    var value = this.currStack.pop();
    if (value < 0) {
      this.currStack.push(Math.ceil(value));
    } else {
      this.currStack.push(Math.floor(value));
    }
  } else if (instruction == ">") {
    var b = this.currStack.pop();
    var a = this.currStack.pop();
    this.currStack.push(+(a > b));
  } else if (instruction == "<") {
    var b = this.currStack.pop();
    var a = this.currStack.pop();
    this.currStack.push(+(a < b));
  } else if (instruction == "=") {
    var b = this.currStack.pop();
    var a = this.currStack.pop();
    this.currStack.push(+(a == b));
  } else if (instruction == "!") {
    this.currStack.push(+ !this.currStack.pop());
  } else if (instruction == "?") {
    this.currStack.push(Math.random());
  } else if (instruction == "n") {
    output = "" + this.currStack.pop();
  } else if (instruction == "o") {
    output = String.fromCharCode(this.currStack.pop());
  } else if (instruction == "r") {
    var input = this.program.io.getNumber();
    this.currStack.push(input);
  } else if (instruction == "i") {
    var input = this.program.io.getChar();
    this.currStack.push(input);
  } else if (instruction == "(") {
    this.length -= Math.floor(this.currStack.pop());
    this.length = Math.max(this.length, 0);
  } else if (instruction == ")") {
    this.length += Math.floor(this.currStack.pop());
    this.length = Math.min(this.length, this.code.length);
  } else if (instruction == "w") {
    this.wait = this.currStack.pop();
  }
  // Any unrecognized character is a no-op
  if (this.ip >= this.length) {
    // We've swallowed the IP, so this snake dies
    this.alive = false;
    this.program.snakesLiving--;
  } else {
    // Increment IP and loop if appropriate
    this.ip = (this.ip + 1) % this.length;
  }
  return output;
}
Snake.prototype.getHighlightedCode = function() {
  var result = "";
  for (var i = 0; i < this.code.length; i++) {
    if (i == this.length) {
      result += '<span class="swallowedCode">';
    }
    if (i == this.ip) {
      if (this.wait > 0) {
        result += '<span class="nextActiveToken">';
      } else {
        result += '<span class="activeToken">';
      }
      result += escapeEntities(this.code.charAt(i)) + '</span>';
    } else {
      result += escapeEntities(this.code.charAt(i));
    }
  }
  if (this.length < this.code.length) {
    result += '</span>';
  }
  return result;
}

// Define Program class
function Program(source, speed, io) {
  this.sharedStack = new Stack();
  this.snakes = source.split(/\r?\n/).map(function(snakeCode) {
    var snake = new Snake(snakeCode);
    snake.program = this;
    snake.sharedStack = this.sharedStack;
    return snake;
  }.bind(this));
  this.snakesLiving = this.snakes.length;
  this.io = io;
  this.speed = speed || 10;
  this.halting = false;
}
Program.prototype.run = function() {
  this.step();
  if (this.snakesLiving) {
    this.timeout = window.setTimeout(this.run.bind(this), 1000 / this.speed);
  }
}
Program.prototype.step = function() {
   for (var s = 0; s < this.snakes.length; s++) {
    var output = this.snakes[s].step();
    if (output) {
      this.io.print(output);
    }
  }
  this.io.displaySource(this.snakes.map(function (snake) {
      return snake.getHighlightedCode();
    }).join("<br>"));
 }
Program.prototype.halt = function() {
  window.clearTimeout(this.timeout);
}

var ioFunctions = {
  print: function (item) {
    var stdout = document.getElementById('stdout');
    stdout.value += "" + item;
  },
  getChar: function () {
    if (inputData) {
      var inputChar = inputData[0];
      inputData = inputData.slice(1);
      result = inputChar.charCodeAt(0);
    } else {
      result = -1;
    }
    var stdinDisplay = document.getElementById('stdin-display');
    stdinDisplay.innerHTML = escapeEntities(inputData);
    return result;
  },
  getNumber: function () {
    while (inputData && (inputData[0] < "0" || "9" < inputData[0])) {
      inputData = inputData.slice(1);
    }
    if (inputData) {
      var inputNumber = inputData.match(/\d+/)[0];
      inputData = inputData.slice(inputNumber.length);
      result = +inputNumber;
    } else {
      result = -1;
    }
    var stdinDisplay = document.getElementById('stdin-display');
    stdinDisplay.innerHTML = escapeEntities(inputData);
    return result;
  },
  displaySource: function (formattedCode) {
    var sourceDisplay = document.getElementById('source-display');
    sourceDisplay.innerHTML = formattedCode;
  }
};
var program = null;
var inputData = null;
function showEditor() {
  var source = document.getElementById('source'),
    sourceDisplayWrapper = document.getElementById('source-display-wrapper'),
    stdin = document.getElementById('stdin'),
    stdinDisplayWrapper = document.getElementById('stdin-display-wrapper');
  
  source.style.display = "block";
  stdin.style.display = "block";
  sourceDisplayWrapper.style.display = "none";
  stdinDisplayWrapper.style.display = "none";
  
  source.focus();
}
function hideEditor() {
  var source = document.getElementById('source'),
    sourceDisplay = document.getElementById('source-display'),
    sourceDisplayWrapper = document.getElementById('source-display-wrapper'),
    stdin = document.getElementById('stdin'),
    stdinDisplay = document.getElementById('stdin-display'),
    stdinDisplayWrapper = document.getElementById('stdin-display-wrapper');
  
  source.style.display = "none";
  stdin.style.display = "none";
  sourceDisplayWrapper.style.display = "block";
  stdinDisplayWrapper.style.display = "block";
  
  var sourceHeight = getComputedStyle(source).height,
    stdinHeight = getComputedStyle(stdin).height;
  sourceDisplayWrapper.style.minHeight = sourceHeight;
  sourceDisplayWrapper.style.maxHeight = sourceHeight;
  stdinDisplayWrapper.style.minHeight = stdinHeight;
  stdinDisplayWrapper.style.maxHeight = stdinHeight;
  sourceDisplay.textContent = source.value;
  stdinDisplay.textContent = stdin.value;
}
function escapeEntities(input) {
  return input.replace(/&/g, '&amp;').replace(/</g, '&lt;').replace(/>/g, '&gt;');
}
function resetProgram() {
  var stdout = document.getElementById('stdout');
  stdout.value = null;
  if (program !== null) {
    program.halt();
  }
  program = null;
  inputData = null;
  showEditor();
}
function initProgram() {
  var source = document.getElementById('source'),
    stepsPerSecond = document.getElementById('steps-per-second'),
    stdin = document.getElementById('stdin');
  program = new Program(source.value, +stepsPerSecond.innerHTML, ioFunctions);
  hideEditor();
  inputData = stdin.value;
}
function runBtnClick() {
  if (program === null || program.snakesLiving == 0) {
    resetProgram();
    initProgram();
  } else {
    program.halt();
    var stepsPerSecond = document.getElementById('steps-per-second');
    program.speed = +stepsPerSecond.innerHTML;
  }
  program.run();
}
function stepBtnClick() {
  if (program === null) {
    initProgram();
  } else {
    program.halt();
  }
  program.step();
}
function sourceDisplayClick() {
  resetProgram();
}
.container {
    width: 100%;
}
.so-box {
    font-family:'Helvetica Neue', Arial, sans-serif;
    font-weight: bold;
    color: #fff;
    text-align: center;
    padding: .3em .7em;
    font-size: 1em;
    line-height: 1.1;
    border: 1px solid #c47b07;
    -webkit-box-shadow: 0 2px 2px rgba(0, 0, 0, 0.3), 0 2px 0 rgba(255, 255, 255, 0.15) inset;
    text-shadow: 0 0 2px rgba(0, 0, 0, 0.5);
    background: #f88912;
    box-shadow: 0 2px 2px rgba(0, 0, 0, 0.3), 0 2px 0 rgba(255, 255, 255, 0.15) inset;
}
.control {
    display: inline-block;
    border-radius: 6px;
    float: left;
    margin-right: 25px;
    cursor: pointer;
}
.option {
    padding: 10px 20px;
    margin-right: 25px;
    float: left;
}
h1 {
    text-align: center;
    font-family: Georgia, 'Times New Roman', serif;
}
a {
    text-decoration: none;
}
input, textarea {
    box-sizing: border-box;
}
textarea {
    display: block;
    white-space: pre;
    overflow: auto;
    height: 50px;
    width: 100%;
    max-width: 100%;
    min-height: 25px;
}
span[contenteditable] {
    padding: 2px 6px;
    background: #cc7801;
    color: #fff;
}
#stdout-container, #stdin-container {
    height: auto;
    padding: 6px 0;
}
#reset {
    float: right;
}
#source-display-wrapper , #stdin-display-wrapper{
    display: none;
    width: 100%;
    height: 100%;
    overflow: auto;
    border: 1px solid black;
    box-sizing: border-box;
}
#source-display , #stdin-display{
    font-family: monospace;
    white-space: pre;
    padding: 2px;
}
.activeToken {
    background: #f93;
}
.nextActiveToken {
    background: #bbb;
}
.swallowedCode{
    color: #999;
}
.clearfix:after {
    content:".";
    display: block;
    height: 0;
    clear: both;
    visibility: hidden;
}
.clearfix {
    display: inline-block;
}
* html .clearfix {
    height: 1%;
}
.clearfix {
    display: block;
}
<!--
Designed and written 2015 by D. Loscutoff
Much of the HTML and CSS was taken from this Befunge interpreter by Ingo Bürk: http://codegolf.stackexchange.com/a/40331/16766
-->
<div class="container">
<textarea id="source" placeholder="Enter your program here" wrap="off">Sr0s1(
)S1+.@@.@@%!Ms+S.@@.@>6*(6s2=n1(</textarea>
<div id="source-display-wrapper" onclick="sourceDisplayClick()"><div id="source-display"></div></div></div><div id="stdin-container" class="container">
<textarea id="stdin" placeholder="Input" wrap="off">5</textarea>
<div id="stdin-display-wrapper" onclick="stdinDisplayClick()"><div id="stdin-display"></div></div></div><div id="controls-container" class="container clearfix"><input type="button" id="run" class="control so-box" value="Run" onclick="runBtnClick()" /><input type="button" id="pause" class="control so-box" value="Pause" onclick="program.halt()" /><input type="button" id="step" class="control so-box" value="Step" onclick="stepBtnClick()" /><input type="button" id="reset" class="control so-box" value="Reset" onclick="resetProgram()" /></div><div id="stdout-container" class="container"><textarea id="stdout" placeholder="Output" wrap="off" readonly></textarea></div><div id="options-container" class="container"><div class="option so-box">Steps per Second:
<span id="steps-per-second" contenteditable>20</span></div></div>

\$\endgroup\$
3
\$\begingroup\$

Vitsy, 2 bytes

Yes, it's that Simple...x.

pN
   Implicit grab of STDIN as number, if possible.
p  If it's prime, push 1 to the stack. Else, push 0.
 N Output as number.

Interestingly, adding an i to this will also find prime characters.

ipN

For input % (ASCII character 37) will output 1.

\$\endgroup\$
1
  • \$\begingroup\$ Haha, so punny! +1 from me. \$\endgroup\$ Commented Nov 7, 2015 at 19:00
3
\$\begingroup\$

Jelly, 4 bytes

’!²%

Try it online!

Jelly has a built-in for primality testing (ÆP, 2 bytes), but it uses a probabilistic method.

This answer uses Wilson's theorem instead. For input x, it calculates (x - 1)!² % x, which yields 1 if x is a prime number and 0 if not.

        Input: x

’       Decrement; compute x - 1.
 !      Apply factorial atop the previous result. Yields (x - 1)!.
  ²     Apply square atop the previous result. Yields (x - 1)!².
   %    Do a modulus hook; compute (x - 1)!² % x.
\$\endgroup\$
3
\$\begingroup\$

Par, 9 bytes

Counted using its own, non-UTF-8 encoding.

✶↓″↑p~1=*

Explanation:

✶          Parse the input (which is
             implicitly on the stack).    n
 ↓         Subtract one.                  (n-1)
  ″        Duplicate.                     (n-1)  (n-1)
   ↑       Add one.                       (n-1)  n
    p      Prime divisors. For 1, this
             strangely returns (1).       (n-1)  np
     ~     Length.                        (n-1)  np~
      1=   Is the length one? This is
             iff n isn't composite.       (n-1)  noncomposite(n)
        *  Multiply the top of stack.     (n-1)*noncomposite(n)
\$\endgroup\$
3
\$\begingroup\$

Binary-Encoded Golfical, 13+1 (-x flag) = 14 bytes

This can converted to the standard graphical version using the included Encoder utility, or run directly by adding the -x flag.

Hex dump:

00 40 02 15 14 49 1b 00 00 00 01 17 17

The original image:

enter image description here

Zoomed in 100x with color value lables:

enter image description here

Explanation:

10,0,0->Input number
14,3,0->Turn right if prime
11,0,1->Go east
0,0,0->Set to 0
0,0,1->Set to 1
10,1,0->Print number
\$\endgroup\$
3
\$\begingroup\$

Arcyóu, 42 7 bytes

Note: I added a builtin for primality testing after I submitted this answer. In the interest of completeness, I have left the old answer below, but this is the new official answer:

(p?(#(l

Primality check on a line of input casted to int.


Old answer:

((F(n)(?([ n)(&(f x(_ 2 n)(% n x)))f))(#(l

Arcyóu is a LISP-like golfing language of my own devising.

Explanation:

((F(n)               ; Anonymous function taking one argument n
  (? ([ n)           ; If-statement with condition n-1 (handling the special case)
    (&               ; & is both bitwise AND and an 'all' function
      (f x (_ 2 n)   ; For loop iterating over a range from 2 to n
        (% n x)))    ; n mod x
    f))              ; If n did equal 1, return false
(# (l                ; Now call the function on a line of input casted to int                 

The interpreter allows you to leave off final close-parens, since adding them back is trivial.

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

MediaWiki templates with ParserFunctions, 101 + 1 = 102 bytes (for title)

{{#ifexpr:{{{n}}} mod {{{f|(n-1)}}}==0|false|{{#ifexpr:{{{f}}}==1|true|{{:p|n=n|f={{#expr:f-1}}}}}}}}

Ungolfed:

{{#ifexpr:{{{n}}} mod {{{f|(n-1)}}}==0|false|
    {{#ifexpr:{{{f}}}==1|true|
        {{p|n=n|f={{#expr:f-1}}}}
    }}
}}

This recursive trial division method theoretically works, but to determine the primality of a positive integer n, $wgMaxTemplateDepth (in the MediaWiki config) must exceed n - 2.

\$\endgroup\$
2
  • \$\begingroup\$ So, in practice, this works for no single input? According to the rules, it must work at least for integers 1 to 255... \$\endgroup\$
    – Dennis
    Commented Dec 21, 2015 at 20:25
  • \$\begingroup\$ This solution is valid for wikis that allow at least a recursive depth of 253. \$\endgroup\$
    – DuhHello
    Commented Dec 21, 2015 at 20:29
3
\$\begingroup\$

Befunge 93, 44 bytes

&:v>0.@       @.-1<
03<_v#%p03+1:g03::_^#`g

This works by trial division.

There's a hidden unprintable character between the v> on the first line; it's the character whose value is 2. The base64 of the file is as follows:

Jjp2Aj4wLkAgICAgICAgQC4tMTwKMDM8X3YjJXAwMysxOmcwMzo6X14jYGc=

Opening it as hex in Sublime Text looks like this (newline confusion, though):

263a 7602 3e30 2e40 2020 2020 2020 2040
2e2d 313c 0d0a 3033 3c5f 7623 2570 3033
2b31 3a67 3033 3a3a 5f5e 2360 670d 0a

Try this out here.

\$\endgroup\$
1 2 3
4
5
13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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