205
\$\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
  • 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\$ @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

302 Answers 302

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 
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Python 3, 42 55 bytes

n=int(input());print(sum(n%m<1 for m in range(1,n))==1)

Try it online!

The n%m<1 comparison is sufficient to check that n is a multiple of m. I start the range at 1 to correctly handle the case n == 1.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Go, 231 bytes

package main
import."fmt"
type c chan int
func main(){a,k:=0,make(c);Scan(&a);go func(d c){for i:=2;;i++{d<-i}}(k)
for{p:=<-k;if a==p||a<p{Print(a==p);break};j:=make(c)
go func(i,o c,p int){for{j:=<-i;if j%p!=0{o<-j}}}(k,j,p);k=j}}

This solution contains a sieve that generates primes, when the primes exceed the candidate, or there is a match it outputs true for primes and false for non-primes.

The main code is blatantly stolen from this playground example.

Since it is rather silly I probably wont be golfing this solution any further

Try it online!

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Python 2, 51 bytes

p=input()
print all(p%i for i in range(2,p-1))==1<p

Try it online!

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Procedural Footnote Language, 41 bytes

[1]
[PFL1.0]
[1] [PRIME:[INPUT]]
[PFLEND]

Explanation

This program is fairly straight-forward: The body of the document (above the [PFL1.0] tag) is the result/output, and is equivalent to the evaluated contents of footnote [1]. Footnote [1] evaluates to the result of the [PRIME] function on input from STDIN.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Reality, 1 byte

P

This takes input via stdinput and return true if it is a prime and false other wise


Alternate :

If taking input is not allowed then

p number

space is not required (replace number with your number)


Note : Reality is an under-development language and was created after this challenge

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Racket, 67 42 bytes

(require math/number-theory)(prime?(read))

When run in DrRacket, this will prompt the user for an integer and return #f (false) if the number is not a prime and #t (true) if the number is a prime.

Previous (and much more complicated) version:

((λ(l)(or(= l 1)(ormap(λ(x)(=(modulo l x)0))(range 2 l))))(read))
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Z80Golf, 30 bytes

00000000: 040c 0934 0c28 0d0a b720 f960 6909 38f4  ...4.(... .`i.8.
00000010: 2534 18f9 24cd 0380 6f7e cd00 8076       %4..$...o~...v

Try it online!

Takes a single-byte input. Outputs a zero byte for prime byte values, and some non-zero byte for composite values. (This value is actually the number of distinct prime divisors!)

Disassembly:

  inc b
  inc c
  add hl, bc  ; HL = BC = $0101.
              ; We use $0100~$ffff as a prime sieve array.
  inc (hl)    ; Mark 1 as composite.

next:
  inc c       ; Loop for C from 2 to 255.
  jr z, done
  ld a, (bc)
  or a
  jr nz, next ; If *BC is marked as composite, skip.

  ; sieve
  ld h, b     ; Mark *(BC), *(2*BC-256), *(3*BC-512) ... as composite.
              ; (So for BC = $0103, this is $0103 $0106 $0109 ...)
  ld l, c
clear:
  add hl, bc
  jr c, next  ; Run until HL overflows! This is more work than necessary, but shorter.
  dec h
  inc (hl)
  jr clear

done:          ; Now H = 0.
  inc h        ; Now H = 1.
  call $8003
  ld l, a      ; Now HL = $0100 + input.
  ld a, (hl)
  call $8000   ; putchar(*HL)
  halt
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Elixir, 122 bytes

o=fn f,p,1->1
f,1,c->0
f,p,c->case rem(p,c)do
0->0
_->f.(f,p,c-1)end end
{i,_}=Integer.parse IO.gets""
IO.puts o.(o,i,i-1)

Try it online!

Can definitely be golfed. Outputs 1 for prime and 0 for composite

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ This breaks on 1. Otherwise, replacing True by 0<1 and False by 1<0 shortens it a bit. \$\endgroup\$ – Ørjan Johansen Jun 21 '18 at 18:03
  • \$\begingroup\$ 1 has been fixed, and I just switched True / False out for the easier int equivalents \$\endgroup\$ – Dave Jun 21 '18 at 18:49
1
\$\begingroup\$

Scala, 40 bytes

def f(n:Int)= !(2 to n-1).exists(n%_==0)

Try it online!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Unfortunately, this challenge doesn't allow functions. \$\endgroup\$ – Dennis Jun 25 '18 at 13:49
1
\$\begingroup\$

Julia 0.6, 44 bytes

n=parse(Int,ARGS[]);show(sum(n%(1:n).<1)==2)

Try it online!

Since the existing answers are invalid for the challenge and/or outdated by newer Julia versions, I'm adding a Julia answer that works in Julia 0.6.

For Julia 0.7 (and to avoid deprecation warnings in 0.6), this needs just one more byte (% becomes .%):

45 bytes

n=parse(Int,ARGS[]);show(sum(n.%(1:n).<1)==2)

Try it online!

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Foam, 9 bytes

;# #.% .#

Foam isn't on TIO yet, but it should be coming soon!

Outputs 1 for prime and 0 for nonprime.

Foam has a prime checking builtin.

;#   <- read number
#.%  <- is number prime?
.#   <- output number
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Flobnar, 25 bytes

%\ @
:&|\<
-:1>
1*<
>>  *

Try it online!

Outputs 1 for prime, 0 for composite. Uses the -d flag to get numerical input. Be aware that the time it takes for each number doubles, where an input of 18 will take ~6 seconds, and 19 takes ~12 seconds. This is because the algorithm (based on Wilson's theorum) looks somewhat like:

def f(n):
    if n == 0:
        return 1
    else:
        return n*f(n-1)*f(n-1)
print f(input)*f(input)%input

So basically the function takes 2n+1 steps, doubling the time it takes for each step. If you want to test the code itself, you can use this (+2 bytes) which is merely 2n steps. It basically removes the surplus extra call of f(n-1) in the return of the function.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Elixir, 75 72 bytes

n=String.to_integer IO.gets""
IO.puts Enum.all?2..n-1,&rem(n,&1)>0||2==n

Try it online!

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Pixiedust, 59 bytes

Takes input in the ++ register, and leaves output in the .. register.

*.+*.*+.
+.
.++*++
+*..
**+..+++*
*+++*+*.*+
+**
+..
.*...*

Explanation

* . +* .*+.       Set the +* register to 2 - this is the factor being checked
+.                Define a label whose name is the empty string
. + +* ++         Test whether +* has reached ++ yet
+* . .            If it has, go to the "." label
* *+ .. ++ +*     Set the branch register to ++ modulo +*
* ++ +* +* .*+    Increment the factor
+* *              If the branch register is not 0 (meaning it's not a factor) restart the loop
+. .              The "." label
. * .. .*         Invert the .. register
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Cardinal, 24 21 bytes

Thanks to @Jo King for golfing off 3 bytes

Code:

%
:
=>-!.
v#~M!@
-
R^

Try it online!

Explanation:

%      //Start program
:      //Read input
=      //Copy input to inactive value
v#     //Loop around and pass copy of pointer up and to right after each loop
-      //Decrement active value by 1
R^     //End program if input=1

*>-!.     //If active value =1 print 0 (occurs just before line below ends program)
*#~M!@    //If inactive value divisible by active value end program
**
**
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

F#, 79 84 bytes

Fixed as per Dennis's suggestion.

stdin.ReadLine()|>int|>fun n->not(Seq.exists(fun i->n%i=0)[2..n-1]||n=1)|>printf"%b"

Now works for input = 1. Can be run same as before.


Original submission:

I didn't see an F# answer so...

stdin.ReadLine()|>int|>fun n->not(Seq.exists(fun i->n%i=0)[2..n-1])|>printf"%b"

Can be compiled with fsc or run directly in fsi. Takes a newline-terminated string from stdin and spits out a bool to stdout when run.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Unfortunately, that doesn't work for input 1. Try it online! \$\endgroup\$ – Dennis Dec 27 '18 at 20:59
  • \$\begingroup\$ Remember, lambdas are allowed, so... 44? \$\endgroup\$ – ASCII-only Jan 31 '19 at 8:38
1
\$\begingroup\$

C#, 116 bytes

Non fancy full program entry (cherry-picking some stuff from java):

class P{static void Main(string[] a){int i=2,n=int.Parse(a[0]);for(;i<n;)n=n%i++<1?0:n;System.Console.Write(n>1);}}
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

C++ (gcc), 85 bytes

#include<iostream>
int main(){int n,d=1;for(std::cin>>n;n%++d%n;);std::cout<<(n==d);}

Try it online!

  • -2 bytes thanks to @ceilingcat

Ungolfed

#include <iostream>
int main() {
    int n,d=1;                      
    for (std::cin >> n; n % ++d      // Trial division. If n dividible by d, end.
                          % n        /* No effect when n > 1.
                                        But required to make sure the loop ever ends if n == 1
                                     */
                            );
        ) { /* Empty loop body */ }  /* d is now the lowest number greater than 1 which
                                        divides n (or 2 if n == 1)
                                     */
    std::cout << (n==d);             // If that number is n, n must be prime.

}

Port of my Ink answer. Competitive in multiple other languages. I wasn't going to post this, but I couldn't find a C++ compiler that would compile the existing C++ answer.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ @ceilingcat well spotted, thanks \$\endgroup\$ – Sara J Jun 3 '19 at 18:34
1
\$\begingroup\$

K (oK), 14 19 bytes

Solution:

2=+/d=_d:x%!x:. 0:`

Try it online!

Example:

root@c957fa0dccbd:/ok# echo 1 | node repl.js examples/prime.k
0
root@c957fa0dccbd:/ok# echo 2 | node repl.js examples/prime.k
1
root@c957fa0dccbd:/ok# echo 5 | node repl.js examples/prime.k
1
root@c957fa0dccbd:/ok# echo 97 | node repl.js examples/prime.k
1

Explanation:

Calculate number of factors for input, if equal to 2, then it's prime.

2=+/d=_d:x%!x:. 0:` / the solution
                0:` / read from stdin
              .     / value (ie convert "123" > 123)
            x:      / store input as x
           !        / range 0..x
         x%         / x divided by ...
       d:           / store as d
      _             / floor
    d=              / d equal to ...
  +/                / sum
2=                  / 2 equals?
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Ink, 68 51 bytes

-(l)
+(n)[+]
->l
*(r)[{n}]
{n%(r+1)%n:->r|{n==(r+1)}}

Ink was made for writing interactive fiction. It was never meant to be a general-purpose programming language. So it only has one way to recieve input.
Choice prompts.
So the way it works is, if option 2 is labelled with the number you want to check, you pick option 2. Otherwise you pick option 1 to increment option 2's label. So, if you want to check if 15 is prime, you'd input

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2

TIO doesn't handle this, unfortunately.

-17 bytes by using read counts of named options instead of creating variables. This brings the overhead of taking input this way down to something like 24 characters (or even 18 if we don't care about minimising the text from the prompts), compared to the 10 for defining a parametrised stitch and returning from it.

Since full programs can use global variables and read counts, but stitches that have to be reusable can't, using full programs might actually pay off in places where I thought it wouldn't. Neat.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

T-SQL, 116 bytes

WITH t AS(SELECT 2n UNION ALL SELECT n+1FROM t WHERE n<5e4)
SELECT*FROM z,t WHERE p%n=0AND n<p OPTION(MAXRECURSION 0)

There is an Oracle SQL answer here, but couldn't find a Microsoft T-SQL version for this classic question.

Notes:

  • Line break is for readability only.
  • Returns no rows if prime, returns 1 or more rows otherwise. This is allowed per this output rule.
  • Input is taken via pre-existing table \$z\$ with INT field \$p\$, per this input rule.
  • Handles values of \$p\$ up to the max value of the INT type, \$2^{31}-1\$

Explanation:

Generates an in-memory number table \$t\$ from 2 to 50k (which exceeds the square root of the max int), then joins to the input table \$z\$ and uses the modulo operator % to test for divisibility. Any values that divide evenly are returned, so an empty result means the input is prime.

OPTION(MAXRECURSION 0) is needed to recursively generate a table with more than 100 rows, unless you've altered this configuration setting on your SQL server.

Optimized for bytes, not speed; checks more values than is strictly necessary.

| improve this answer | |
\$\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 F, 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.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

W d, 5 bytes

(Possibly the only <=5-byter that does not use a prime or number factorization built-in?) (The two spaces here represent a tab)

àTéBΦ

repr'd:'‡T\tB⑸'

Unpacked:

m!Wk2=

Explanation

This is really difficult to read, so an explanation will be nice.

    W    % (implicit) Foreach the inclusive range from 1 to the input:
bam      % The "bam" magic! Just kidding. Evaluates b % a
         % Since b is out-of-bounds, this takes the upper-level input
         % as the operand.
   !     % Remove those that aren't valid multiples.
     k   % Is the length of the array ...
      2= % ... equal to 2?
         % i.e. primes have exactly 2 factors: 1 and itself
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Crax! That sounds like a good golfing language name. \$\endgroup\$ – Lyxal Jan 1 at 6:16
  • \$\begingroup\$ I'm more saying that the source code looks like it says CRAX \$\endgroup\$ – Lyxal Jan 1 at 6:19
  • \$\begingroup\$ Looks like there is a bug in the interpreter and I had to change the compression... \$\endgroup\$ – user85052 Jan 20 at 0:14
1
\$\begingroup\$

Keg, 43 36 6 4 bytes (SBCS)

@MPƒ

-2 bytes using a BFL function

乁( ⏒ ͜ʖ ⏒ )ㄏ

Answer History

6 bytes

:;¡²$%

Try it online!

-30 bytes thanks to @JoKing

No TIO as it needs to be updated due to a bug found with the ² operator.

Transpiles to:

from KegLib import *
from Stackd import Stack
stack = Stack()
printed = False
duplicate(stack)
decrement(stack)
factorial(stack)
square(stack)
swap(stack)
maths(stack, '%')

if not printed:
    printing = ""
    for item in stack:
        if type(item) is Stack:
            printing += str(item)

        elif type(item) is str:
            printing += custom_format(item)
        elif type(item) == Coherse.char:
            printing += item.v

        elif item < 10 or item > 256:
            printing += str(item)
        else:
            printing += chr(item)
    print(printing, end="")

36 bytes (SBCS)

 ¿®n21®t{:©n≠©t0≠*|:©n$%[1|0]®t1+}©t.

Try it online!

-7 bytes by not using a variable to keep track of the count.

Explained

¿®n21®t{:©n≠©t0≠*|:©n$%[1|0]®t1+}©t.
¿®n                                 #Take the number to check and store it in variable n
   2                                #This will act as the divisor counter
    1®t                             #This will act as the return value, indicating the primality
       {:©n≠©t0≠*|                  #While the counter isn't equal to n and there isn't a divisor yet
                  :©n$%             #Take the counter and number, then swap for modulus
                       [1|0]®t      #Depending upon the result set t to 1 if it doesn't divide otherwise 0
                              1+}   #Increment the counter
                                 ©t.#Print the result

43 bytes (SBCS)

¿®n2®c1®t{©c©n≠©t0≠*|©n©c%[1|0]®t©n1+®c}©t.

It's a real ugly mess, but it works. I'll explain it all later. Also, doesn't work on TIO due to a bug that I found. It should work soon however.

Use the latest github interpreter

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

cQuents, 3 bytes

?pZ

Try it online!

Explanation

Usually, I'd put the commands here, but I feel like that wouldn't be enough.

? outputs if the input is in the sequence. Item 1: Z returns 0, as Z returns the previous item, and Item 0 is always 0. p finds the next prime number (2). Item 2: Z returns 2. p finds the next prime number, which I thought would be 2, but no, it returns 3.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Haskell + Parsec, 181 bytes, no math

import Text.Parsec
a=anyChar
g s=a>>= \c->try(many1$string$c:s)*>eof<|>g(c:s)
main=readLn>>= \x->print$0<case parse(try(a*>eof)<|>(pure<$>a>>=g))""$replicate x '0'of{Left _->1;_->0}

Try it online!

Ungolfed and explanation:

import Data.Either (isLeft)
import Text.Parsec (eof, (<|>), try, anyChar, many1, string, parse)
import Text.Parsec.String (Parser)

-- Successfully parses any string of nonprime length, and fails on all others.
-- Exactly one character is not prime. If more than one character exists, we recurse with `go`.
notPrime :: Parser ()
notPrime = try (anyChar *> eof) <|> (pure <$> anyChar >>= go)
    -- `go cs` reads a character `c` and determines whether the remaining input is `c:cs` repeated.
    -- If so, the parse succeeds. If not, we call `go (c:cs)` to read another character and test again.
    where go :: String -> Parser ()
          go cs = do
                  c <- anyChar
                  try (many1 $ string $ c:cs) *> eof <|> go (c:cs)

-- Checks whether the parser `notPrime` fails on a uniform string of the specified length
isPrime :: Int -> Bool
isPrime n = isLeft $ parse notPrime "" (replicate n '\0')

Try it online!

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

qalc/Qalculate, 8 bytes

If reading from any variable is allowed:

p-1)!²%p

Otherwise 12 bytes:

ans−1)!²%ans

The great thing about "programming" in a calculator is that you can basically just enter formulas directly.

Example usage in Bash for the "ans" case:

echo "5" | qalc -t -f - "ans−1)! ²%ans"

Note that I added a space after the exclamation mark only because Bash otherwise tries to interpret "" as an "event". It's not actually required by qalc, which can be seen by for example creating this file:

5
(ans−1)!²%ans

…and then executing it with qalc -t -f test.txt.

Other consoles or other ways of calling qalc than Bash might not have this problem.

The calculation can also be entered in "interactive mode" by simply running qalc -t, entering the number and then entering the expression on the next input. This also works in the GUI program "Qalculate".

Meta explanation:

The output is 0 for non-prime numbers and a positive integer for prime numbers. I let this run in a loop for all numbers up to 10000 and it was always 1 for prime numbers, but I haven't checked whether that is guaranteed yet.

This solution is based on this Labyrinth answer. I essentially just found something (qalc) that has all the parts of the formula as builtins instead of having to program all the parts myself on a lower level.

The -t argument hides the interpreted calculation, so that the output of the example command looks like this:

5
1

…instead of like this:

5 = 5
rem(factorial(ans - 1)^2, ans) = 1

Reading the number in in qalc is difficult. It has a system of variables, but I haven't figured out how to set those in the CLI yet. In the GUI it's pretty easy. That's one of the main reasons why I also provided a solution with "ans".

Inserting the number into the formula two times would mean modifying the "program", which is surely not allowed.

There seems to be no way to execute multiple expressions non-interactively with qalc, except by reading in a file. In this case, I used - as a "file", which is StdIn, and used that only to store the input in ans, which is implicitly done by qalc. You could also use an actual file and use the number in that file as input. Or you could even say that ans is already the input of the "program", in which case the program is simply the 12 bytes seen above, or even any variable, then the 8 byte solution.

Algorithm explanation:

The Wikipedia article linked in the Labyrinth answer looks pretty confusing, but the principle is easy:

(6-1)!²%6 = 1·1·2·2·3·3·4·4·5·5%6
          = 1·1· 6 · 6 ·4·4·5·5%6
          = 6 ·   something    %6
          = 0

This works because every non-prime number is the product of at least two factors that are smaller than that number. Prime numbers aren't, which leads to something like this:

(5-1)!²%5 = 1·1·2·2·3·3·4·4%5
          = 1·1·2·2·3·3·4·4%5
(no multiplication of those factors results in anything divisible by 5)
          = 1

The squaring is necessary in case there is only one prime factor and that occurs twice:

(9-1)!²%9 = 1·1·2·2·3·3·4·4·5·5·6·6·7·7·8·8%9
          = 1·1·2·2· 9 ·4·4·5·5·6·6·7·7·8·8%9
          = 9 ·         something          %9
          = 0

I originally wrote this answer for TI-Basic:

fPart((Ans-1)!²/Ans

That's just 10 bytes, but it fails on the input 13 already, due to floating point imprecisions in those large numbers (12!²=229442532802560000). So the only difference to an even/odd checker within the working range is 9 and it does not fulfil the criterion to work up to 255. For inputs above 42 it even crashed from an overflow (42!²>10¹⁰⁰).

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

STATA, 62 bytes

di _r(a)
gl c=$a-1
forv b=2/$c{
if!mod($a,`b') gl c=0
}
di $c

Ungolfed

display _request(number)
global maxtest = $number-1
forvalues counter=2/$maxtest{
    if !mod($number,`counter') global $maxtest = 0
}
display $maxtest

This tests every integer from 2 to number-1 for divisibility. By printing number-1 as the output, it prints a 0 for an input of 1. Today I learned that STATA has truthy/falsey values. Previously I assumed I could only use (in)equalities in conditions. Note: this does not yet work in the online interpreter and is only valid in the proprietary STATA interpreter.

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Mathematica, 33 bytes or 61 bytes

Two answers are provided:

Manipulate[PrimeQ[n],{n,1,255,1}]


<<PrimalityProving`
Manipulate[ProvablePrimeQ[n],{n,1,255,1}]

As explained in the implementation documentation, PrimeQ[] is known to produce correct output for arguments less than 10^16 (though is widely believed, on heuristic arguments, to be correct for any input). (User Charles claims this bound can be increased to 2^64 ~= 10^19 in an answer here.) It tests for small primes, uses Miller-Rabin with bases 2 and 3, then uses a Lucas test. ProvablyPrimeQ[] uses a much slower testing procedure, Atkin-Morain (reference with further citations), but is known to be correct and can produce a certificate of primality or witness of compositeness, if desired. So, PrimeQ[] meets the challenge (255 is much less than 10^16), but ProvablyPrimeQ[] meets the specification "primality test" without reservation.

These wrap the PrimeQ[] call into a widget for user interaction. See the docs for a visual example. This widget provides a slider over the range 1 to 255 with unit increments. Next to the slider is a button to provide additional controls: a textbox for direct input and "playback" controls. It's interesting (at most, three times :-) ) to watch this widget iterate through the range.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ The rule for hardcoding are "If (and only if) your language is unable to accept any kind of user input" (emphasis mine). Mathematica can take user input, so I believe it needs to use that (see this answer for an example). \$\endgroup\$ – Sp3000 Sep 13 '15 at 12:50
  • \$\begingroup\$ @Sp3000 : Huh. Did not know about Input[]. So, ..., is the local protocol to withdraw the whole solution, or keep the documentation that the solution you cite (and many others here) do not provably test for primality? \$\endgroup\$ – Eric Towers Sep 13 '15 at 23:55
  • \$\begingroup\$ @Sp3000 : I now also perceive a bit of a gap between the rule you reference and the other rule "If your language is able to read from STDIN or accept command-line arguments". I certainly can't make Mathematica do that (and I think this negative capability is why I went the way I did). But I agree that Mathematica meets the description you have. Yet I can imagine settings where neither clause applies. \$\endgroup\$ – Eric Towers Sep 13 '15 at 23:59
  • \$\begingroup\$ The rule you mention was indeed badly phrased, so I've rephrased it. However, the rule Sp3000 mentioned clearly stated that hardcoding is only allowed if there are no alternatives. Since Mathematica has Input[], your three snippets are invalid in its current form. \$\endgroup\$ – Dennis Sep 14 '15 at 3:59
  • \$\begingroup\$ @Dennis : The third snippet receives user input, as described. \$\endgroup\$ – Eric Towers Sep 14 '15 at 6:33

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