196
\$\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\$
  • \$\begingroup\$ Can I take inputs as negative numbers, where abs(input) would be the number I am testing? \$\endgroup\$ – Stan Strum Sep 6 '17 at 3:40
  • 1
    \$\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\$ – Lyndon White Dec 12 '17 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 Dec 12 '17 at 12:51
  • 1
    \$\begingroup\$ @Shaggy Seems like a question for meta. \$\endgroup\$ – Dennis Jun 25 '18 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 Jun 25 '18 at 13:45

290 Answers 290

1
\$\begingroup\$

TI-BASIC (nspire), 15 bytes

f(n):=isPrime(n

Uses the CAS isPrime() builtin. The environment by default adds an extra parenthesis on the end of the input, making it f(n):=isPrime(n) when the function is defined in the interpreter.

\$\endgroup\$
  • \$\begingroup\$ I'm assuming nspire doesn't allow unclosed parentheses? \$\endgroup\$ – Zacharý Aug 24 '17 at 0:24
  • \$\begingroup\$ Yeah, it autocloses them. \$\endgroup\$ – user50198 Aug 24 '17 at 0:36
  • \$\begingroup\$ I don't think that the TI-Nspire runs TI-BASIC. I was under the impression that it used a variant of Lua... \$\endgroup\$ – Scott Milner Aug 24 '17 at 0:38
  • \$\begingroup\$ It also uses a form of lua for code in documents, but it does use basic for on-calculator programming (without an interpreter page) \$\endgroup\$ – user50198 Aug 24 '17 at 0:39
  • \$\begingroup\$ If it autocloses them, then isPrime(n should work. \$\endgroup\$ – Zacharý Aug 24 '17 at 0:44
1
\$\begingroup\$

Pyth, 3 2 bytes

I can't see a simpler way of doing this. My ignorance continues to amaze me.

P_

Explanation (if it needs one):

P   Prime function: factorization if positive, isPrime if negative
 _  Negate the implicit input

Test suite

\$\endgroup\$
  • \$\begingroup\$ No need to subtract from zero, as _ performs negation. \$\endgroup\$ – Dennis Sep 6 '17 at 3:53
  • \$\begingroup\$ @Dennis I tried that earlier, it didn't seem to work... \$\endgroup\$ – Stan Strum Sep 6 '17 at 3:54
1
\$\begingroup\$

Python 3, 57 bytes

k=int(input());print(all(k%j for j in range(2,k))and k>1)

I think it's pretty self-explanatory.

\$\endgroup\$
  • \$\begingroup\$ @JonathanFrech No. \$\endgroup\$ – 0WJYxW9FMN Sep 22 '17 at 21:15
  • \$\begingroup\$ @JonathanFrech The author of this problem asked for a full program. \$\endgroup\$ – 0WJYxW9FMN Sep 23 '17 at 17:47
1
\$\begingroup\$

Taxi, 1519 1309 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 Zoom Zoom:n.[a]Go to Cyclone:w.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 The Underground:s 1 l 1 r 2 l.Switch to plan "1" if no one is waiting.Pickup a passenger going to Cyclone.Go to Cyclone:n 3 l 2 l.Pickup a passenger going to Divide and Conquer.Pickup a passenger going to The Underground.Go to Divide and Conquer:n 2 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 Trunkers.Pickup a passenger going to Equal's Corner.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 "b" if no one is waiting.Go to The Underground:n 3 r 1 r 2 l.Switch to plan "z" if no one is waiting.[1]'0' is waiting at Writer's Depot.[z]'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.[b]Go to Sunny Skies Park:n.Pickup a passenger going to Cyclone.Go to Zoom Zoom:n 1 r.Switch to plan "a".

Try it online!

Un-golfed with comments:

[ Test for Primality ]
[ Inspired by: https://codegolf.stackexchange.com/q/57617 ]

[ Pickup stdin and triplicate it]
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.
Pickup a passenger going to Cyclone.
Go to Cyclone: north 1st left 1st left 2nd right.
Pickup a passenger going to Cyclone.
Pickup a passenger going to The Underground.
Go to Zoom Zoom: north.

[a]
Go to Cyclone: west.
Pickup a passenger going to Sunny Skies Park.
Pickup a passenger going to Divide and Conquer.

[ Store a copy of the original stdin ]
Go to Sunny Skies Park: north 1st right.

[ Iterate down to the next lowest number ]
[ If the input is 1, the switch will immediately output '0' ]
Go to The Underground: south 1st left 1st right 2nd left.
Switch to plan "1" if no one is waiting.
Pickup a passenger going to Cyclone.
Go to Cyclone: north 3rd left 2nd left.
Pickup a passenger going to Divide and Conquer.
Pickup a passenger going to The Underground.

[ Divide the original by the current iteration and check if it's an integer ]
Go to Divide and Conquer: north 2nd right 2nd right 1st right.
Pickup a passenger going to Cyclone.
Go to Cyclone: east 1st left 1st left 2nd left.
Pickup a passenger going to Trunkers.
Pickup a passenger going to Equal's Corner.
Go to Trunkers: south 1st left.
Pickup a passenger going to Equal's Corner.
Go to Equal's Corner: west 1st left.
Switch to plan "b" if no one is waiting.

[ Someone was waiting so it was an integer result ]
[ This is going to eventually happen when we divide by one ]
[ If the current iteration is 1, we want to return 1 as a truthy result ]
[ It it's anything higher than 1, we want to return 0 as a falsey result ]
Go to The Underground: north 3rd right 1st right 2nd left.
Switch to plan "z" if no one is waiting.

[1]
'0' is waiting at Writer's Depot.
[z]
'1' is waiting at 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.
[ No need to return to taxi garage or even switch to the end of the program ]
[ It will output to stderr because it can't drive in the next direction and terminate the program ]

[b]
[ No one was waiting so it was not an integer result ]
[ Continue on to the next iteration ]
Go to Sunny Skies Park: north.
Pickup a passenger going to Cyclone.
Go to Zoom Zoom: north 1st right.
Switch to plan "a".

The only thing that felt golf-y when writing it was allowing it to error out instead of terminate properly.

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

Funky, 39 bytes

n=>{o=1for(i=2;i<n;i++)o=o&0<n%i o&n>1}

Try it online!

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

Common Lisp, 64 bytes

(print(=(loop as x from 1 to(setq n(read))count(=(rem n x)0))2))

Try it online!

57 bytes in Common Lisp REPL:

(=(loop as x from 1 to(setq n(read))count(=(rem n x)0))2)
\$\endgroup\$
1
\$\begingroup\$

Groovy, 92 91

i=System.in.newReader().readLine()as int
print i==2||i>1&&!(true in(2..i-1).collect{i%it<1})

Such a verbose way to read from stdin...

\$\endgroup\$
  • \$\begingroup\$ Welcome to Programming Puzzles & Code Golf! \$\endgroup\$ – Dennis Sep 26 '15 at 1:44
  • \$\begingroup\$ Can you remove the space between ) and as? \$\endgroup\$ – HyperNeutrino Nov 10 '17 at 1:11
  • \$\begingroup\$ @HyperNeutrino Good catch! \$\endgroup\$ – Kleyguerth Nov 10 '17 at 18:54
1
\$\begingroup\$

><>, 46 Bytes

i> :1\/ln;
~\?:-/^?(2l~
%$}:{<;n0/?
l1- ?/1n;\

Takes input as an ascii character, prints 1 for primes, 0 for non-primes, including 1. Loops forever if input is 0 or negative.

How it works:

 > :1\
 \?:-/

Fills the stack with integers between 0 and input, inclusive.

      /ln;
~    /^?(2l~

Removes the top two values on the stack, 0 and 1. Tests if the length of the stack is <2; if it is, the value is either 1 or 2. In either case, its truthy/falsy value is the length of the stack; print it. If the length is greater than 2, it continues to the next loop.

%$}:{<;n0/?
l1- ?/1n;\

Duplicates the value being tested from the bottom of the stack. Test if it's divisible by the value at the top. If it is, print 0. Otherwise, check that the stack length is not 1. If it is, the value being tested is prime; print 1.

Edit:

Added on to this program a bit, as a part in my attempt to conquer as much of project euler as possible in ><>.

This is for Project Euler 7: Calculating the 10001st prime

a:::***31[\>?!/l1-?\]r1-:?!/r:nao1+70.
\/{*::+1<0<\%$}:{  <~~
 \:}(?!\/-1l  \         ;nr\
\!?:-1:<\ ?!\~^.38
            \] 1+70.

Comes in at 130 Bytes, although I didn't try very hard to golf it. Pushes 10000 to the stack (since we start at 3), makes a new stack, runs the primality test on the number, starting at 3. If it's prime, decrement the counter and increase the value being tested. If its not prime, just increment the value.

The go-fish interpreter was a life saver for this--it ran orders of magnitude faster than fish.py.

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

Julia, 15 7 bytes

isprime

knocked down 8 bytes thanks to caird coinheringaahing

\$\endgroup\$
  • 1
    \$\begingroup\$ Can you just submit isprime as a function submission? \$\endgroup\$ – caird coinheringaahing Dec 9 '17 at 18:07
  • \$\begingroup\$ i suppose so? good point \$\endgroup\$ – EricShermanCS Dec 10 '17 at 4:32
  • 2
    \$\begingroup\$ This doesn't work in julia 0.6+, (isprime was deprecated in 0.5 and moved to the Primes.jl package). I guess retitle this as Julia 0.5? \$\endgroup\$ – Lyndon White Dec 12 '17 at 6:56
  • \$\begingroup\$ The challenge spec requires a full program. Also, isprime uses a probabilistic primality test and is thus cannot be used for this challenge. \$\endgroup\$ – Dennis Dec 12 '17 at 12:56
1
\$\begingroup\$

AnyDice, 68 bytes

function: p A {loop N over {2..A/2}{if A/N*N=A {result:0}}result: 1}

I was wondering if AnyDice counted as a language for PCG.se purposes, and it turns out it does,

This is trial division, making use of the fact that AnyDice only supports integer (truncating) division.

usage:

TryIt

output [p 333332]

outputs 0(100%)

output [p 333331]

outputs 1(100%)

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

SNOBOL4 (CSNOBOL4), 105 bytes

	N =INPUT
	X =1
	GT(N,1)	:F(C)
I	X =X + 1
	OUTPUT =EQ(X,N) 1	:S(END)
C	OUTPUT =EQ(REMDR(N,X)) 0	:F(I)
END

Try it online!

I thought about putting my explanation in all caps, but that would just look silly.

This is the brute force approach: Test if N==1, and output 0 on success, then increment X. If we reach a point where X==N, then we have found a prime number and we output 1 and terminate. If we reach a point where N %% X == 0, then we output 0.

I am still learning to golf in SNOBOL, so I think it should be possible to make this shorter.

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

JavaScript, input unary '1'*n, 33 Bytes

!/^(1+1)\1+$/.test(x=prompt())&x>1
\$\endgroup\$
1
\$\begingroup\$

Implicit, 30 29 21 bytes

<2è;:(-1>1?{;|_ñè};).

Try it online!

Whew, another 10 bugs uncovered during the writing of this program. This uses trial division.

While SimpleStack uses a ... stack, I'm going to call two stack values variables. The input will be variable i and the trial-division loop counter will be variable m. Note I might've messed up this explanation somewhere along the road of golfing.

<2è;:(-1>1?{;|_ñè};).
                       implicit input i
<2                     push i < 2
  è                    exit without implicit output if truthy
   ;                   pop i < 2
    :                   set m to input
     (.............)    do
      -1                 decrement m
        >1               push m > 1
          ?{.....}       if true
            ;             pop m > 1
             |            duplicate stack (stack: i, m -> i, m, i, m)
              _           push i % m
               ñ          compute logical NOT on i % m (truthy if i % m falsy)
                è         exit without implicit output if truthy
                  ;      pop top of stack (NOT(i % m) or m > 1)
                   )    while m > 0
                    .   increment

If the input is 0 or 1, it will print nothing, so the output will be falsy. If the input is not prime, the second è exits without implicit output (making hte output empty and therefore falsy). If the input is prime, it will reach the end of the program, and the top of stack will always be 0. . increments it, turning it to 1 (truthy). Implicit output.

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

095, 35 bytes

1Xid1.=(DD,,{d_.%(yX]D}dYs]D1.=[1s]

Returns 0 for composite and 1 for prime.

Explanation:

1X                                  ~ Set True to X
  id                                ~ Take input and duplicate
    1.=                             ~ Check if equal to 2
       (DD                          ~ If not, delete last two items
          ,,                        ~ Subtract 2
            {                       ~ For that many times,
             d_.%                   ~ see if iterator divides into input
                 (yX]               ~ If it does, set False to X
                     D}             ~ Delete last item, close loop
                       dYs]         ~ Duplicate input, print X
                           D1.=[1s] ~ If input = 2, say True
\$\endgroup\$
1
\$\begingroup\$

17, 102

17 is a language I made a few days ago and am now trying out some challenges with.

A single ascii character is taken as input and 0 is returned for false, its lowest factor for true.

0{1 # 2 # 1 + : 2 @
% 0 == 2 * 2 # 1 # == 3 * + 0 @ }2{2 # $$ 0 @}5{0 $$ 0 @}777{0 0 @ I 1 @ 1 2 @}

Expanded:

0 {
  1 # 2 # 1 + : 2 @
  % 0 == 2 * 2 # 1 # == 3 * + 0 @
}
2 {
  2 # $$ 0 @
}
5 {
  0 $$ 0 @
}
777 {
  0 0 @ I 1 @ 1 2 @
}

17 starts at block 777 and runs blocks depending on value stored at 0.

Block 777: Set value 0 to 0, set value 1 to ascii code of input char, set value 2 to 1.

Block 0(first run after block 777): Increase 2 by 1, if 1 mod 2 == 0, go to block 2 unless value 1 is value 2, then goto block 5

Block 2: Load 2 and print, then exit

Block 5: Print 0 and exit

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

SmileBASIC, Forty Four 43 bytes

INPUT N
FOR D=1TO N
P=P+!(N MOD D)NEXT?P==2

Just checks if the number has exactly 2 divisors.

\$\endgroup\$
  • \$\begingroup\$ You could test if P<3 it's one byte shorter and it covers the 1 cornercase. \$\endgroup\$ – steenbergh Feb 19 '17 at 9:01
1
\$\begingroup\$

COBOL (GNU), 305 bytes ( +5 for compiler flags)

ID DIVISION.PROGRAM-ID.A.DATA DIVISION.WORKING-STORAGE SECTION. 1 I PIC 9(9). 1 V PIC 9(9). 1 R PIC 9(9). 1 Q PIC 9(9). 1 P PIC 9 VALUE 1.PROCEDURE DIVISION.ACCEPT V PERFORM VARYING I FROM 2 BY 1 UNTIL I=V DIVIDE I INTO V GIVING Q REMAINDER R IF R=0 THEN MOVE 0 TO P END-IF END-PERFORM DISPLAY P STOP RUN.

Compile with -free flag. (This allows ignoring formatting.)

Try it online!

Ungolfed version:

IDENTIFICATION DIVISION.    *> Required in every program header.
PROGRAM-ID. A.

DATA DIVISION.
WORKING-STORAGE SECTION.
    01 I PIC 9(9).          *> Loop index
    01 V PIC 9(9).          *> Value to test
    01 R PIC 9(9).          *> Remainder
    01 Q PIC 9(9).          *> Quotient
    01 P PIC 9 VALUE 1.     *> Is prime?

PROCEDURE DIVISION.
    ACCEPT V                                    *> Get value from input
    PERFORM VARYING I FROM 2 BY 1 UNTIL I>V/2   *> for (i = 2; i <= v/2; i++)
        DIVIDE I INTO V GIVING Q REMAINDER R    *>     Q = V/I; R = remainder(V/I)
        IF R=0 THEN MOVE 0 TO P END-IF          *>     If remainder is zero, not prime
    END-PERFORM
    DISPLAY P               *> Output result (1 or 0)
    STOP RUN.
\$\endgroup\$
1
\$\begingroup\$

Forth (gforth), 73 61 57 bytes

: f { n } 0 n 1 > if 1 n 2 ?do n i mod 0> * loop then . ;

Try it online!

Stack-Only variant, 76 68 64 61 bytes

: f 0 over 1 > if 1+ over 2 ?do over i mod 0> * loop then . ;

Try it online!

Explanation

0 over             \ place a 0 on the stack then place a copy of the input on top
1 >                \ check if the top of the stack is greater than 1
if                 \ if true execute the if, otherwise skip it
   1+              \ add 1 to our tracking variable (so replace 0 with 1) 
   over 2          \ place n and 2 on the top of the stack, 
   ?do             \ loop from 2 to n, skip loop if n = 2
      over i mod   \ get the modulo of n and the loop index (so n % i) 
      0>           \ check if modulo is greater than 0 (not divisible)
      *            \ multiply bool (-1 or 0) by the top of the stack (shorter version of and)
   loop            \ end the loop 
then               \ end the if statement
.                  \ output the top of the stack
\$\endgroup\$
1
\$\begingroup\$

Pyt, 1 byte

Try it online!

Implicit input
ṗ   primality test
Implicit output
\$\endgroup\$
1
\$\begingroup\$

K, 23 bytes

x=&/(y*/:y:!x)?'x:0$0:`

yay for algorithmic improvements!

Explanation

No operator precedence kind of acts against us here, so we have to resort to paranthesis

x:0$0:`

reads the input and saves the result to the variable x

y:!x takes the list 0..(x-1) and saves it to the variable x

y*/:y applies * using /:, so every element in y is multiplied by y, creating a matrix

?'x searches every column of the matrix for x, returning the length if x is not found

x=&/ &/ takes the minimum of the list by folding it with the min operator, and then checks if it is equal to x. If not, there should exist a combination of two numbers smaller than x result in x, i.e it is not a prime

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

tinylisp, 23 bytes

There's a library function.

(load library
(prime? 1

(Since tinylisp is incapable of taking user input, "For scoring purposes, submit the program that corresponds to the input 1.")

Try it online!


Here's a 112-byte solution using only the base language, no library functions:

(d D(q((F A N)(i(l A N)(D F(a F A)N)(e N A
(d _(q((F N)(i(D F 0 N)(e F N)(_(a 1 F)N
((q((N)(i(e N 1)0(_ 2 N))))1

The first line defines a function D that takes a factor F, an accumulator A (initially 0), and a number N; it returns 1 if N is divisible by D, 0 otherwise.

The second line defines a function _ that takes a minimum factor F and a number N; it returns 1 if N is coprime to all numbers from F to N-1, 0 otherwise.

The third line constructs an anonymous function that takes a number N; it returns 0 if N is 1, and otherwise calls _ with number N and minimum factor 2. As above, the scored code calls the anonymous function with an argument of 1.

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

Zephyr, 88 bytes

input n as Integer
set f to 0
for i from 1to n
if(n mod i)=0
inc f
end if
next
print f=2

Try it online!

Uses the "n must have exactly two perfect divisors in the inclusive range [1, n]" approach. Run a for loop over that range, count the numbers i for which n mod i is zero, and output at the end whether the count equals 2.

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

><>, 23 22 bytes

:1vn%$*:~<
@*>$1-:?!^:

Try it online!

Uses Wilson's theorem again, i.e. (n-1)!**2 %n returns 1 if n is prime, 0 if it is not. Takes input via the -v flag.

How it Works:

:1v Dupe the value and push a 1 as the total
  >$1-  Decrement the copy
      :?!^  If the copy is 0 go up to the first line
@*>       : Else Multiply the total by the copy and repeat the decrement
If we went up to the first line
        ~< Pop the excess 0
      *:   Square the total
  vn%$     Print the total modulo the original value and exit with an error
\$\endgroup\$
1
\$\begingroup\$

Forked, 57 54 bytes

$P11>p1+"Us'v
    |       |
1%& :-msU"p-:-
    |
  &%<

The dual-fork loop is really beautiful. Try it online! Alternate versions with identical bytecount:

Short explanation

This uses a trial division method, equivalent to this C code:

int isPrime(int n) {
    for (int i = 2; i < n; i++)
        if (n % i == 0)
            return 0;
    return 1;
}

Long, thorough explanation

Before we begin, let us define two values:

  • n: the inputted number, to be tested for primality
  • i: the loop counter for the trial division method

Here's the program's control flow:

---->-------v
    |       |
--- :-------:-
    |
  --<

The forks : compose one big loop. The rightmost fork exits the loop and prints 1 if n-i is zero, i.e. if n mod i is always positive, meaning n has no divisors other than 1 and itself.

The leftmost fork exits the loop and prints 0 if n mod i is zero, meaning n has a divisor other than 1 and itself.

The initial four bytes set up the stack. Let's say the input n is 11.

CODE  STACK    EXPLANATION
$     [n=11]   read integer input n
 P    []       pop n, stash in register
  1   [i=1]    push i (initially 1)
   1  [i=1, 1] push filler value for later popping

The code p1+"Us' between the redirects > and v pushes n-i.

CODE    STACK        EXPLANATION
p       [i=1]        pop top of stack (useless value or result of n%i)
 1+     [i=2]        add 1 to top of stack
   "    [i=2, 2]     duplicate top of stack
    U   [i=2, 2, 11] copy register onto stack
     s  [i=2, 11, 2] swap top two stack values
      ' [i=2, 9]     subtract top two stack values

Then the IP turns South and forks. If n-i is zero, it turns East and immediately wraps around to hit 1%& (push 1, print, exit), therefore returning a truthy value if If there are still values of i to check, the IP turns West, hitting the code that computes n mod i:

CODE  STACK        EXPLANATION
p     [i=2]        pop n-i
 "    [i=2, 2]     duplicate top of stack
  U   [i=2, 2, 11] copy register to stack
   s  [i=2, 11, 2] swap top two stack values
    m [i=2, 1]     compute n mod i

The IP is forked, turning South and returning 0 if n mod i is 0. Otherwise it turns North and immediately turns East, where i is incremented and the whole loop is done again.

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

Quarterstaff, 94

golfed 1!

10-?[-38a a a a a a a a a a>a10-?]a>b b[>b>d a>c c[1>c1d>d b d(.>e|>d1>e)c]e f>f1b]2-f(.|1)48!

Try it online!

How it works:

Quarterstaff has a register i call "value", and multiple other registers i call variables, which are referenced by name.

value starts as 0

10 add 10 to value

- multiply value by -1 (value now -10) (this is because it checks for the end of the integer by checking for newline, which has a charcode of 10)

? add an inputted characters charcode to the value (which will be 48 for "0", for example)


the first loop:

[ begin while loop. these work like brainf***'s while loops, but instead of a cell, it uses the value.

- multiply value by -1

38 add 38 to value

At this point, the program has 0 if the most recently input character was "0", -1 if it was "1", -2 if it was "2" etc.

a a a a a a a a a a this is a reference to the variable a 10 times. this means we add 10*a to the value. a starts of as zero

>a store this value in a. this means we have just done the following: a=10*a-int(inputted_char). a is always a negative number when using digits. when the loop is done, a will hold the inputted number *-1. this also happens to set the value to 0. assignment with > always sets the value to 0

10-? this is the same code as we executed before entering the loop. this means that we will input a new character, but if we got to the end of the number, we exit the loop.

] loop end. if the value is zero, we exit, otherwise returning to the start. this while loop executes until it has taken all the input into the variable a in negation (22 becomes -22)


a now holds the negative of the inputted number. why is it negative? well, because it's shorter. if we want to decrease the magnitude by 1, we only have to add 1, not use -, add 1, then use - again.

a>b the a adds a to the value (which is now exactly a because it was previously 0), and >b puts this value into b. in effect b=a, because the > sets the value back to 0. remember a and b are negative

b there is a space in between variable names, because otherwise they get parsed as one name. this just makes the value b, because the value was 0 before


another while loop

[ begin the loop

>b this puts the value inside b, and value now = 0. at the first execution of the loop, this has no effect apart from value = 0, but at subsequent executions, it will be adding 1 to b, which will decrease it in magnitude until reaches -1. we use b to represent divisors

>d value will always be 0 when executing this. this will set d to 0. this is necessary because it is set to other values later in the loop

a>c means c=a. remember a is negative, and so is c

c value += c (value =c because value was 0). c is negative,

[ nested while loop. tests for the value of c in first and subsequent executions because the value is set to c just before it checks. This loop performs modulus

1>c because we have c in the value, this means add 1 to c. remember c is never >0. this makes c a counter down to 0

1d>d add 1 to d (value was 0 before these commands). d is a non-negative integer

b d value += b + d. because b is negative and d is positive, this means that the value will now equal 0 iff abs(b)=abs(d).

(.>e|>d1>e) this is an if else expression/command thing. because it immediately follows the b d which is 0 iff the absolute values of b and d are equal, it means it will execute the else iff abs(b)=abs(d), otherwise the then part. so, the part that executes if the value isn't 0 is .>e. . sets the value to zero, >e puts that 0 in e. e is 0 by default. if b and d have equal magnitude though, >d1>e executes. this puts 0 in d (because the value was zero if we're executing this part) and then 1 in e. if this is the last execution of the loop, it means that we will exit the loop with 1 in e, which represents being divisible. otherwise we haven't finished the modulo process yet. if we executed the if not 0 part and this was the last execution, we exit with 0 in e, representing not divisible.

c value = c (because value was 0 before)

] close nested loop.

back to the not modulus part

e f>f value =0 prior to execution, and f += e (f = e + f)

1b this sets the value to b+1 (remember b is negative). this will get stored in b next execution of the loop, if there is one.

] close outer loop


tying up

2-f value (which equals 0) += f-2. prime numbers exited the modulus loop with e=1 precisely 2 times.

(.|1)48 if that isn't 0, set value to 0, but if it is 0, set to 1. then add 48, to the value, which is either 1 or 0.

! print character with the corresponding char code. thus, print "1" (49) for primes and "0" (48) for not primes

\$\endgroup\$
  • \$\begingroup\$ You can save a byte by moving the >e out of the if expression: Try it online! \$\endgroup\$ – wastl Apr 7 at 12:04
1
\$\begingroup\$

Triangularity, 7 bytes

.).
IEp

Try it online!

Triangularity, 49 bytes

Much more interesting solution, without using built-ins for divisors / prime test. Outputs 1 if the input integer is a prime, 0 otherwise.

....)....
...If)...
..rF@)I..
.f/Df={L.
)2=......

Try it online!

How it works?

Removing the characters that make up for the triangular padding, here's what the program does:

)If)rF@)If/Df={L)2= || Full program. ToS = Top of the Stack
)I                  || Get the 0th input.
  f                 || And cast it to an integer.
   )r               || Create the integer range [0 ... ToS - 1).
     F        {     || Filter the elements of this list which satisfy this function:
      @)If/Df=      || Runs each (X) on a separate stack, keeps those that yield 1.
      @             || Increment X.
       )If/         || And divide the input by it.
           D        || Duplicate, push two copies of the ToS.
            f=      || Floor the second copy and compare it with the first one.
               L    || Length.
                2=  || Check if it equals 2. Implicitly output the result.
\$\endgroup\$
1
\$\begingroup\$

Whispers v2, 27 bytes

>>> ⊤ℙ
> Input
>> 1∘2

Try it online!

Whispers v1, 27 bytes

> Input
>> 1’
>> Output 2

Try it online!

Uses the builtin prime tester. Alternatively, instead of using a builtin, the following code uses Wilson's Theorem and weighs in at 54 bytes

> Input
> 1
> 2
>> 1-2
>> 4!
>> 5*3
>> 6%1
>> Output 7

Try it online!

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

Befunge 93, 33 bytes

&10p1 >1+:10g\`v
1.@.0_^#!%\g01:_

Also works by trial division, as the other befunge post, but is substantially shorter.

Interpreter here.

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

Forth, 82 65 bytes

: f 1 ?do i' i mod 0= + loop 0= ;
1 tib dup 9 accept evaluate f .

Ungolfed:

: f                        \ def f(counter, n):
  1 ?do                    \     for i in range(1, n):
    i' i mod 0= +          \         counter -= n % i == 0  # In Forth True == -1
  loop
  0=                       \     return counter == 0
;
1                          \ counter = 1
tib dup 9 accept evaluate  \ n = int(input()) # Forth version inputs 9 digits at most
f .                        \ print(f(counter, n))

It has at least one downside though: Forth echoes back what it accepted, because it is strongly terminal and/or REPL oriented, so feeding it 7 yields 7 -1

Run it!

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

Befunge-93, 28 bytes

&:0\1\1>-#1:__\#0:#*_$:*\%.@

Try it online!

Uses Wilson theorem, i.e. that ((n-1)!^2)%n returns 1 if n is prime else 0.

How It Works:

&:0\1\ Get input n and dupe it, putting a 0 and a 1 in-between
      1>-#1:_ Decrement and dupe until the number is empty
             _\#0:#*_$ Multiply until you reach the zero, yielding (n-1)!
                      :* Square it
                        \% Mod this value by the original value
                          .@ Print the mod and terminate 
\$\endgroup\$

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.