220
\$\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\$ – 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\$ Could a case be made for locking this challenge and posting a new, less restrictive one? \$\endgroup\$ – Shaggy Jun 25 '18 at 12:59
  • 2
    \$\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

325 Answers 325

1
4 5
6
7 8
11
2
\$\begingroup\$

PHP, 51 bytes

An alternative PHP answer, but required the GMP extension to be installed:

<?=gmp_strval(gmp_nextprime($argv[1]-1))==$argv[1];

Simply subtracts 1 from the input and compares the nextprime result against the input

\$\endgroup\$
1
  • \$\begingroup\$ gmp_cmp can save 3 bytes. But unfortunately, that algorithm is only probably correct, not always. +1 anyway for showing it off. :) \$\endgroup\$ – Titus Oct 16 '16 at 14:14
2
\$\begingroup\$

Clojure, 98 bytes

(let[n(Integer/parseInt(read-line))](println(and(not= 1 n)(not(some #(=(rem n %)0)(range 2 n))))))

Uses some to check if the number has any divisors, then negates the result to indicate whether or not it's prime.

A simple function would have only been 59 bytes :(

(fn[n](and(not= 1 n)(not(some #(=(rem n %)0)(range 2 n)))))

Ungolfed:

(let [n (Integer/parseInt (read-line))]
  (println
    (and (not= 1 n) ; 1 is an unfortunate special case
         (not ; Negate to indicate primality
           (some #(= (rem n %) 0) ; Check if n has any divsors...
                 (range 2 n)))))) ; in the range of 2 to (n-1)

There's a previous Clojure answer, but this beats it by a little over 60 bytes

\$\endgroup\$
5
  • \$\begingroup\$ You can also turn Integer/parseInt to read-string to save a further 5 bytes. \$\endgroup\$ – clismique Jul 9 '17 at 11:38
  • \$\begingroup\$ 1: You can replace (not= 1 n) with (> n 1) to handle the edgecase of 1. 2: You can replace (not (some ...)) with (every? ...) and change the condition around a bit. 3: You can swap the fn[n] and the shorthand around to remove a space, like so: #(and(> % 1)(every?(fn[a](>(rem % a)0))(range 2 %))). These three save 7 bytes. \$\endgroup\$ – clismique Jul 9 '17 at 11:46
  • \$\begingroup\$ @Qwerp-Derp Thanks. I'll try to remember to update my answer later today. \$\endgroup\$ – Carcigenicate Jul 9 '17 at 13:09
  • \$\begingroup\$ @Carcigenicate Here's a quick reminder. :P \$\endgroup\$ – totallyhuman Nov 17 '17 at 0:30
  • \$\begingroup\$ @totallyhuman LOL. JULY. I clearly dropped that ball. I hate to delay this again, but I'm not quite on the mental state to deal with this right now. I think I'll set a reminder on my phone \$\endgroup\$ – Carcigenicate Nov 17 '17 at 0:31
2
\$\begingroup\$

Clojure, 124

Full program, reading standard input and writing to standard output as required by the terms.

(let[n(read-string(first *command-line-args*))](print(and(> n 1)(=(reduce #(* %1(if(=(mod n %2)0)0 1))1(range 2 n))1))))

Obviously inefficient to test all the way up to n but trying to be clever with (range 2 (inc (int (Math/sqrt n)))) adds length.

Ungolfed version:

(let
    [n (read-string (first *command-line-args*))]
  (print
   (and
    (> n 1)
    (=
     (reduce #(* %1
                 (if (= (mod n %2) 0)
                   0
                   1)
                 )
             1
             (range 2 n)
             )
     1
     )
    )
   )
  )

Put in file prime.clj, execute as:

java -cp location-of-clojure.jar-in-your-system clojure.main prime.clj 1

E.g. in my system I get:

$ java -cp ../../repo-wide-libs/clojure.jar clojure.main prime.clj  1
false
$ java -cp ../../repo-wide-libs/clojure.jar clojure.main prime.clj  7
true
$ java -cp ../../repo-wide-libs/clojure.jar clojure.main prime.clj  8
false
\$\endgroup\$
2
  • \$\begingroup\$ Is there a way to remove any of those spaces? Since this is Lisp-like, you could probably take out the ones before parentheses. \$\endgroup\$ – jqblz Sep 28 '15 at 13:37
  • \$\begingroup\$ yeah so this overflows easily, just uploaded version that doesn't overflow (3 chars longer) \$\endgroup\$ – Marcus Junius Brutus Jan 6 '17 at 19:26
2
\$\begingroup\$

APL (NARS2000), 6 bytes

Function: 0∘π

Program: 0π⎕

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

Dyalog APL, 10 9 bytes

2=∘≢∘∪⍳∨⊢

I don't think this one has been posted.

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

Jolf, 2 bytes

Try it here!

m{

Simple. m{ is the isPrime function of the math module, and j is the (implicit) user input as a number.

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

Swift 4, 58 bytes

let n=Int(readLine()!)!;print((1..<n).filter{n%$0<1}==[1])

Try it online!

Saved a few bytes thanks to Dennis.

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

Wumpus, 13 bytes

I=&l2-&*=*r%O

Try it online!

Explanation

Uses Wilson's theorem in the form (n-1)!2isprime(n) (mod n) (where isprime gives 0 or 1, respectively).

The implementation doesn't really work the way it's supposed to for n = 1, but the result still ends up being 0.

I=  Read n and duplicate it.
&l  Push the stack depth n times. Since there's another copy of n on the stack to
    begin with, this pushes 1, 2, ..., n-1, n.
2-  Subtract 2 from n.
&*  Multiply the top two numbers that many times. This essentially folds
    multiplication over the range [1,n-1], which computes (n-1)!. At
    the end of this, the stack will be [n, (n-1)!]. However, in the case
    of n = 1, we only ever pushed one element for the range, so there's
    nothing left to form the factorial and the stack contains only one
    copy of 1.
=*  Square the (n-1)!.
r   Reverse the stack. This is normally just used to swap n and (n-1)!²,
    but we're using stack reversal instead of swap (~), so that the stack
    remains unchanged for n = 1.
%   Modulo. For n = 1, this computes 0 % 1 = 0 (because there's an implicit
    zero underneath the 1 on the stack). For all other n, this computes
    (n-1)!² % n, i.e. the result of the primality test.
O   Output the result as a decimal integer.

The IP then bounces off the end of the program and starts moving left again. % tries another modulo, but there's only implicit zeros on the stack, so the program ends due to the attempted division by zero.

\$\endgroup\$
2
\$\begingroup\$

Stax, 2 bytes

|p

Run and debug online!

Added for completeness. An internal.

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

Perl 6, 20 bytes

say get~~$_%%one ^$_

Try it online!

There's also the built-in is-prime, but I thought it would be more interesting to do it without it. Surprisingly, this is only 4 bytes longer.

Explanation:

    get                # Get a line of input
       ~~              # Smartmatch it by setting $_ to input
         $_%%          # Is input divisible by
             one       # Only one of
                 ^$_   # The range 0 to input-1?
say                    # And print

Note that this works because n%%0 is boolified to False.

\$\endgroup\$
2
\$\begingroup\$

05AB1E, 3 bytes

fнQ

find all factors and see if last one equals input.

Try it online!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Built-ins are allowed, so just p is enough. \$\endgroup\$ – Grimmy Mar 29 '19 at 13:32
2
\$\begingroup\$

Gol><>, 4 bytes

ISPh

Thanks to ASCII-only for letting me now I didn't need 2 bytes, since it was redundant.

Try it online!

\$\endgroup\$
4
  • 1
    \$\begingroup\$ The ?1 is needed?????? \$\endgroup\$ – ASCII-only Feb 20 '19 at 16:07
  • \$\begingroup\$ @ASCII-only Thank you for pointing that out, I didn't even think of that. Fixing it now! \$\endgroup\$ – KrystosTheOverlord Feb 20 '19 at 17:23
  • 2
    \$\begingroup\$ At least in this particular implementation of Gol><>, P is implemented by the` is_probably_prime` function. Unfortunately, this challenge requires a deterministic primality test. \$\endgroup\$ – Dennis Feb 20 '19 at 19:37
  • \$\begingroup\$ @Dennis The is_probably_prime function is a wrapper for the sympy isprime function, which is deterministic up to \$2^{64}\$. If the sympy library is not available, then it does a non-deterministic check. \$\endgroup\$ – Jo King Mar 15 '19 at 1:58
2
\$\begingroup\$

dc, 17 22 bytes

?d*5+v[dz%rdz<M*]dsMxp

Try it online!

I've been on a bit of a dc kick lately and although there's already a dc solution here, this is 10 5 bytes shorter. It follows the I/O request of the original question, which does add two bytes for the explicit input and output (rather than the usual rules these days that allow implicit stack I/O), but okay.

This outputs zero for composite numbers and non-zero for primes.

How it works: this program builds a stack consisting of the modulo of the input with the current stack size (so the stack looks like, from bottom to top, i%2, i%3, i%4, ...), then when it decides it's gone far enough (stack size = input) it multiplies the stack as it unwinds the recursion.

\$\endgroup\$
2
  • 2
    \$\begingroup\$ This fails for 1 and 2. \$\endgroup\$ – Ørjan Johansen Mar 16 '19 at 0:22
  • \$\begingroup\$ Oof, you're right. Not sure how I missed that. It took me five bytes to fix (by precomposing with d*5+v, i.e., x -> int(sqrt(x^2+5)), i.e., 1->2, 2->3, n->n for n>2) \$\endgroup\$ – Sophia Lechner Mar 18 '19 at 18:09
2
\$\begingroup\$

GHC 8.2.2, 716 bytes

{-#LANGUAGE FlexibleInstances,FunctionalDependencies,UndecidableInstances,CPP#-}
#define i instance
#define c class
data F
data T
data S n
data C x s
c A p q r|p q->r
i A F q F
i A T q q
c E p x y z|p x y->z
i E F x y y
i E T x y x
c G x y b|x y->b
i G x F T
i G F(S y)F
i G x y b=>G(S x)(S y)b
c M x y z|x y->z
i M x F x
i M F(S y)F
i M x y z=>M(S x)(S y)z
c D x y b|x y->b
i D x F T
i(G(S y)x p,M(S y)x z,D x z q,A p q b)=>D x(S y)b
c K f x y|f x->y
i D m n b=>K(S n)m b
c I f s n|f s->n
i I f F F
i(K f x b,I f s m,E b(S m)m n)=>I f(C x s)n
c R n s|n->s
i R F F
i R n s=>R(S n)(C(S n)s)
c Q m n b|m n->b
i Q F F T
i Q F(S y)F
i Q(S x)F F
i Q x y b=>Q(S x)(S y)b
c P n b|n->b
i(R n s,I(S n)s m,Q m(S(S F))b)=>P n b

Try it online!

This has got to be the most beautiful code I've ever written. It's a compile-time metaprogram that determines whether a type (represented Peano-style, where F is zero and S n is n's successor) is prime.

This works in GHC 8.2.2, the version TIO currently uses. It works locally in 8.8.3 as well. I have included the language extensions in the code, all except one—the TIO example linked above has MonoLocalBinds to suppress a warning. The program works just fine without them.

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

Output has to be written to STDOUT or closest alternative.

As far as I know, metaprograms like this have no means of I/O. With FunctionalDependencies, typeclasses can act much like functions, and in this way, the typeclass P is a "function" from natural numbers to booleans (T and F—yes, the same type represents zero, false, and the empty list). I believe this to be the closest alternative to the standard streams.

The test suite I provided covers numbers from one to twenty. Try changing any T to F or vice-versa, and the program will fail to compile.

I know there are improvements that can be made, and I'll be updating this answer soonish with them.

\$\endgroup\$
2
\$\begingroup\$

DIVCON, 8 bytes

Prequisities: Enter 1 into the INPUT_MAX prompt.

i*[;-=o]

Explanation

"Partition" by * here means solving x * y = a - a is the original accumulator value. x and y needs to be as close as possible. In addition, the following equality must be satisfied: x>=y

         Description     | Example(0) | Example(1)
         ----------------+------------+-----------
i        Take an input   |  12        | 13
 *       Partition by *  | 4, 3       | 13, 1
         ----------------+------------+-----------
  [      Left branch     |   4        | 13
         Do nothing      | *discarded*| *discarded*
         ----------------+------------+------------
   ;     Right branch    | 3          | 1
    -    x - 1           | 2          | 0
     =   x == 0?         | 0          | 1
      o  Print this value| OUT: 0     | OUT: 1
         ----------------+------------+------------
       ] End both branches

Actually, there is another implicit reverse computation. But, since INPUT_MAX is 1, the extra prompting from i is disabled.

\$\endgroup\$
2
\$\begingroup\$

MAWP, 48 46 54 bytes

@1A<:.>{1A<1:.>2M}!1A[/!!\!/P\!/WA<:.>{%}\2A?0{1M}]1:.

-2 bytes from Dion's suggestion.

+8 bytes after fixing the problem with 1 as input.

Prints 1 for prime and 0 for non-prime. Can probably be golfed by a few more bytes, since it checks for 2 at the beginning first.

Try it!

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Should work as expected now. \$\endgroup\$ – Razetime Aug 26 '20 at 9:10
  • \$\begingroup\$ Looks good now. Can you explain how it works? \$\endgroup\$ – Dingus Aug 26 '20 at 9:16
  • 1
    \$\begingroup\$ checks for 1 first, then 2, then moves on with a loop till it finds any divisor. \$\endgroup\$ – Razetime Aug 26 '20 at 9:17
2
\$\begingroup\$

Rockstar, 119 117 bytes

listen to N
let D be N
let P be N aint 1
while P and D-2
let D be-1
let M be N/D
turn up M
let P be N/D aint M

say P

Try it here (Code will need to be pasted in)

\$\endgroup\$
2
\$\begingroup\$

Vyxal, 4 bytes

KL2=

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?

Explained

KL2=
KL   # len(factors(input))
  2= # ^ == 2 // prime numbers have only [1, n] as factors...other numbers have 1 or 3+ factors
\$\endgroup\$
2
\$\begingroup\$

CSASM v2.1.2.2, 207 235 bytes

Prints a 1 (truthy) if the input is a prime integer, 0 (falsy) otherwise.
Truthy values in CSASM are non-zero numbers, non-\0 chars and non-null strings/arrays/objects.
Falsy values in CSASM are zero, the \0 character or null strings/arrays/objects.

func main:
in ""
conv i32
pop $a
push $a
push 2
comp.gte
push $f.o
brtrue a
br b
.lbl a
push 2
dup
pop $1
push $a
sub
brfalse d
.lbl c
clf.o
push $a
push $1
rem
brfalse b
inc $1
push $1
push $a
comp.lt
push $f.o
brtrue c
.lbl d
push 1
print
ret
.lbl b
push 0
print
ret
end

Commented and ungolfed:

func main:
    ; Get the input, convert it to an integer and store it in the accumulator
    in ""
    conv i32
    pop $a

    ; if $a < 2, then $a is not prime
    push $a
    push 2
    comp.gte
    push $f.o
    brtrue initLoop
    br notPrime

    .lbl initLoop
    ; Initialize the loop counter and check if $a == 2
    ; If $a is 2, return truthy early
    push 2
    dup
    pop $1
    push $a
    sub
    brfalse prime

    .lbl loop
        ; Clear the comparison flag
        clf.o

        ; If $a % $1 == 0, then $a is not prime
        push $a
        push $1
        rem
        brfalse notPrime

        ; Loop until $1 >= $a
        inc $1
        push $1
        push $a
        comp.lt
        push $f.o
        brtrue loop

    .lbl prime
    ; $a is prime
    push 1
    print
    ret

    .lbl notPrime
    ; $a is not prime
    push 0
    print
    ret
end
\$\endgroup\$
2
\$\begingroup\$

JavaScript (ES6), 28 bytes

f=(n,i=n)=>n%--i?f(n,i):i==1

Try it online!

Old, 33 bytes:

f=(n,t=2)=>t<n?n%t?f(n,t+1):0:n>1
\$\endgroup\$
2
  • \$\begingroup\$ That's 28 bytes, is it not? \$\endgroup\$ – Recursive Co. May 10 at 5:23
  • \$\begingroup\$ @ophact I don't even know how it's possible to mess that up lol, fixed. \$\endgroup\$ – Redwolf Programs May 10 at 12:16
2
\$\begingroup\$

Knight, 24 bytes

O&-=x+0P=iT?x;W%x=i+1iNi

Prints true for primes, false for composite numbers.

# print the output of the entire body
OUTPUT
  # If the number's one, then `&` returns `false`. otherwise we execute the rhs.
  &

    # `>` will coerce `i` to a number, and return `TRUE` unless `x` is one.
    >
      = x (+ 0 PROMPT) # set `x` to the input value
      = i TRUE

    # We know `x` is prime if the first `i` that `%x i` is zero for is `x`.
    ?
      x
      ;
        # evaluate the while loop then discard it.
        # note that `+ 1 i` will coerce the initial `TRUE` to a `1`.
        WHILE % x (= i + 1 i)
          NULL # ignore the body

        # the return value of `;` is `i` here. It'll be equal to `x` for primes.
        i
\$\endgroup\$
2
\$\begingroup\$

<>^v, 184 bytes

Prints 1 if number is prime, else prints 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\$
1
\$\begingroup\$

Pyth, 8 bytes

&>Q1!tPQ

Alternative that doesn't support values less than 2:

!tPQ
\$\endgroup\$
0
1
\$\begingroup\$

Perl, 35 bytes

Uses regular expressions...

$_=1x$_;s/^(11+?)\g1+$//;print$_>1

That's 34 bytes of code, plus one byte for the -n switch needed to fetch a line from stdin. Outputs 1 if the number is prime, or nothing otherwise

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

Stuck, 3 bytes

iv|

Prints 1 for primes and 0 for non-primes. (The definition of "truthy/falsy values" means I can't use iv, because Stuck prints False/True without knowing what those are.)

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

Scala, 96 bytes

#!/usr/bin/env scala
print(((a:Int)=>if(a==2)true;else!2.to(a-1).exists(a%_==0))(args(0).toInt))

JVM and yet not last place :D

Does use some bash functionality but I'm using Scala so don't be too hard on me.

\$\endgroup\$
3
  • \$\begingroup\$ It's possible in 50 bytes. :) \$\endgroup\$ – Emil Lundberg Sep 24 '15 at 12:07
  • \$\begingroup\$ @EmilLundberg That code won't run. You need a main method or use the same trick I used. \$\endgroup\$ – Martijn Sep 24 '15 at 15:13
  • \$\begingroup\$ Huh, you're right that it doesn't compile as scalac prime.scala. But it does run as scala prime.scala. \$\endgroup\$ – Emil Lundberg Sep 24 '15 at 15:47
1
\$\begingroup\$

K, 29 bytes

(x>1)&&/x!'2_!1+_sqrt x:0$0:`

Got this off Rosetta Code, so marked it as community wiki.

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

XPath 2.0, 45 40 bytes

$i>1 and empty((2 to $i -1)[$i mod .=0])

For readability, incl. non-mandatory spaces (45 bytes)

$i > 1 and empty((2 to $i - 1)[$i mod . = 0])

In XPath, the only way to hand input like an integer to the processor is by passing it a parameter, in this case $i. This is hardly performant, and obvious improvement would be to use:

$i > 1 and empty((2 to math:sqrt($i) cast as xs:integer)[$i mod . = 0])

But since "shortest in any given language" and not performance was the goal, I'll leave the original in.

How it works

For people new to XPath, it works as follows:

  1. Create a sequence up to the current number:

    (2 to $i - 1)
    
  2. Filter all that have a modulo zero (i.e., that divide properly)

    [$i mod . = 0]
    
  3. Test if the resulting sequence is empty, if it non-empty, there is a divisor

    empty(...)
    
  4. Also test for special-case 1:

    $i > 1
    

The query as a whole returns the string true (2, 5, 101, 5483) or false (1, 4, 5487).

As a nice consequence, you can find all divisors (not prime divisors!) using an even shorter expression:

(2 to $i - 1)[$i mod . = 0]

will return (3, 5, 7, 15, 21, 35) for input 105.

\$\endgroup\$
1
4 5
6
7 8
11

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.