234
\$\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\$ Dec 12, 2017 at 6:21
  • 2
    \$\begingroup\$ @LyndonWhite This was intended as a catalog (like “Hello, World!”) of primality tests, so a unified submission format seemed preferable. It's one of two decisions about this challenge that I regret, the other being only allowing deterministic primality tests. \$\endgroup\$
    – Dennis
    Dec 12, 2017 at 12:51
  • 1
    \$\begingroup\$ Could a case be made for locking this challenge and posting a new, less restrictive one? \$\endgroup\$
    – Shaggy
    Jun 25, 2018 at 12:59
  • 2
    \$\begingroup\$ @Shaggy Seems like a question for meta. \$\endgroup\$
    – Dennis
    Jun 25, 2018 at 13:44
  • 1
    \$\begingroup\$ Yeah, that's what I was thinking. I'll let you do the honours, seeing as it's your challenge. \$\endgroup\$
    – Shaggy
    Jun 25, 2018 at 13:45

366 Answers 366

1
7 8
9
10 11
13
1
\$\begingroup\$

Ruby, 33 bytes

A little longer than other solutions, but doesn't require flags:

require'prime';p$*[0].to_i.prime?

Can be run putting in a file, say prime.rb:

ruby prime.rb 97

Or directly on the command line:

ruby -e "require'prime';p$*[0].to_i.prime?" 97

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

Logy, 82 bytes

f[X]->X<2&1|X*f[X-1];p[&1]->0<0;p[X]->f[X-1]%X==X-1;main[A]->print[p[atoi[A(1)]]];

I have no idea what I am doing.

Use Wilson's theorem.

Ungolfed code:

factorial[X] -> X < 2 & 1 | X*factorial[X - 1];
prime[&1] -> FALSE;
prime[X] -> factorial[X - 1]%X == X - 1;
main[Args] -> print[prime[atoi[Args(1)]]];
\$\endgroup\$
1
\$\begingroup\$

Batch, 121 bytes

set i=2
if %1%==2 exit /b
if %1%==1 echo 0
:b
set /a a=%1%%%i%
set /a i=%i%+1
if %i%==%1% exit /b
if %a%==0 echo 0
goto b

Outputs 0 if it's no prime. This works only for inputs input > 0.

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

Dip, 1 byte

P

Pretty self-explanatory...

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

Unary, 165192711826249169871716905363504385377479408598339493836 bytes

Well, basically 165192711826249169871716905363504385377479408598339493836 zeros. Here is a Java program that prints the actual program:

public class Main{
  public static void main(String[]args){
    for(BigInteger i = new BigInteger("165192711826249169871716905363504385377479408598339493836"),BigInteger j = BigInteger.ZERO;j.compareTo(i)!=0;j = j.add(BigInteger.ONE)){
      System.out.println("0");
    }
  }
}

This a port of this Brainfuck answer.

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

memes, 2 bytes

I decided to hop on the language train. Code:

}"

Explanation:

} //Takes next input.
" //Returns `True` or `False`, representing if the input is prime.
\$\endgroup\$
1
\$\begingroup\$

Ceylon, 107 112

That was my first try:

shared void p(){if(exists a=process.readLine(),exists c=parseInteger(a)){print(!(2:c-2).any((d)=>c%d<1));}}

This is a simple trial division of all numbers between 2 and c - 1, using the range operator : and the any method for iterating.

But this will also note 1 as prime. So here the corrected version:

shared void p(){if(exists a=process.readLine(),exists c=parseInteger(a)){print(1<c&&!(2:c-2).any((d)=>c%d<1));}}

That works for numbers up to 2^63-1 ... and takes quite long for larger primes (or composite numbers with large factors) – I think it took about half a minute to confirm 2147483647 (=2^31-1) as prime.

The formatted version:

shared void p() {
    if (exists a = process.readLine(),
        exists c = parseInteger(a)) {
        print(1 < c && !(2 : c - 2).any((d) => c % d < 1));
    }
}

I originally wrote the check as d.divides(c), but the modulo operator is so much shorter.

As a bonus, here is a variant for arbitrary size integers, though there is not really a point in using this due to the slowness.

import ceylon.math.whole {
    w=parseWhole,
    t=two,
    o=one
}
shared void q() {
    if (exists a = process.readLine(),
        exists c = w(a)) {
        print(c == t || !(t .. c - t).any((d) => c % d < o));
    }
}

The : range operator needs an Integer (the number of elements) as a second argument, so we use the .. operator, which takes the same type as the first argument, i.e. here a Whole, as second argument (the upper limit). 2..c-1 is the same as 2:c-2 for large c, but this becomes an empty list for two (and a non-empty list for one), so we need a different exception here than in the Integer version. It becomes mainly longer due to the imports.

The space-reduced version has length 153:

import ceylon.math.whole{w=parseWhole,t=two,o=one}shared void q(){if(exists a=process.readLine(),exists c=w(a)){print(c==t||!(t..c-o).any((d)=>c%d<o));}}
\$\endgroup\$
1
\$\begingroup\$

Maverick, 25 bytes

(1:(<>@-1)//$*)%<>@=<>@-1

Try it online!

This is a pretty fun language IMO. Infix and esoteric.

(1:(<>@-1)//$*)%<>@=<>@-1
 1:                         range from 1 to
   (<>@                     first command line arg (<> called with no args)
       -1)                  minus 1
          //$*              folded over multiplication
(             )%            modulus
                <>@         the input
                   =        does the above equal
                    <>@-1   the input minus 1? If so, yields prime
\$\endgroup\$
1
\$\begingroup\$

Valyrio, 14 bytes

s∫main [ipo]

Outputs 1 if the input is prime. Otherwise outputs 0.

Explanation

s∫ tells the interpreter to enter stack mode

main [ starts the main code block

i takes an input and evaluates it

p pushes 1 or 0 to the stack depending on primality

o outputs the top item on the stack

] ends the main code block

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

Racket 75 bytes

(let p((c 2))(cond[(> c(sqrt n))#t][(= 0(modulo n c))#f][else(p(+ 1 c))]))

Ungolfed:

(define (f n)                 ; COMMENTS: 
  (let loop ((c 2))
    (cond
      [(> c (sqrt n)) #t]     ; if no divisor found till sq root of number, it must be a prime
      [(= 0 (modulo n c)) #f] ; if divisor found, it is not a prime
      [else (loop (add1 c))]  ; try with next number
      )))

Following version is longer but more efficient for checking larger numbers since it keeps & uses previously found prime numbers:

(λ(N)(define(p n(o'(2))(c 2))(cond[(> c n)o][(ormap(λ(x)(= 0(modulo c x)))o)
(p n o(+ 1 c))][else(p n(cons c o)(+ 1 c))]))(= N(car(p N))))

Ungolfed version:

(p=subfunction to build prime number list till n; o= list of prime numbers found; c=current number being checked)

(define f
  (λ (N) 
    (define (p n (o '(2)) (c 2))
      (cond
        [(> c n) o]
        [(ormap (lambda(x) (= 0 (modulo c x))) o)
                (p n o (add1 c)) ]
        [else (p n (cons c o) (add1 c))]))
    (= N (first (p N)))))

Testing:

(f 109)
(f 10)
(f 11)
(f 12)
(f 13)
(f 49)
(f 43)
(f 57)
(f 47)

Output:

#t
#f
#t
#f
#t
#f
#t
#f
#t
\$\endgroup\$
1
  • \$\begingroup\$ If I understand correctly, the solution given is a snippet, not a full program, because it inputs from the variable n. \$\endgroup\$ Apr 24, 2017 at 6:43
1
\$\begingroup\$

PHP, 43 39 54 44 43 bytes

improved my answer from stackoverflow:

for($i=$n=$argv[1];--$i&&$n%$i;);echo$i==1;

Run with -r. prints 1 if argument is prime, empty string else.

loops $i down from $n-1 until it finds a divisor of $n; $n is prime if that divisor is 1.

6 bytes extra for the 1 case. almost happy.

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

√ å ı ¥ ® Ï Ø ¿ , 3 bytes

Ipo

p is the primality test.

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

NO!, 34 bytes

This was taken from the NO! GitHub page. It isn't mine

NOOOOOOO?NOOOOOOOOOOO
NOOOOOOOO?no
\$\endgroup\$
1
  • 1
    \$\begingroup\$ This should be marked as community wiki if you didn't write it. \$\endgroup\$ May 11, 2017 at 14:09
1
\$\begingroup\$

Ruby 16+15 bytes

require 'prime';p->e{e.prime?}
\$\endgroup\$
1
\$\begingroup\$

QBIC, 21 20 3 bytes (nc)

Since the purpose of the challenge is to build a catalog, I feel it's important to keep the QBIC post up-to-date with the current state of the language:

­?µ:

Explanation:

?    PRINT
 µ   QBIC's prime test, returns -1 for primes, 0 otherwise
  :  Read a number from the command line, insert that here
     The function is closed automatically because of EOF.

Previously, at 20 bytes:

:[a|~a%b|\p=p+1}?p<3

Simple trial divider. Every time b (the loop counter) cleanly divides a (our prime-candidate), p is increased. Primes will end with p at 2 (or p=1 for a=1). This then prints -1 for primes, and 0 for non-primes, which are QBasic default values for true and false resp.


Original entry, 21 bytes. This prints 1 for primes, and 0 for others. This feels more 'natural' to me than QBasic's default -1/0. Also, this only does slightly less than a/2 divisions for primes (and quits when it detects a non-prime), instead of doing a divisions regardlessly.

:[2,a/2|~a%b=0|_Xp}?q

Explanation:

:       Get the input number, 'a'
[2,a/2| FOR(b=2, b<=(a/2), b++)
~a%b=0  IF a MOD b == 0     --> Clean division == no prime
|_Xp    THEN exit program, printing 'p' (which never gets set and is 0 by default)
}       Close all language constructs: IF/END IF, FOR/NEXT
?q      We've made it through the FOR loop without division, N is prime.
        In QBIC, 'q' is auto-initialised to 1, '?' prints it.
\$\endgroup\$
1
\$\begingroup\$

Add++, 14 17 bytes

D,f,@,P
+?
$f,x
O

Try it online!

10 bytes are boilerplate for the full program requirement.

Function, 7 bytes

D,f,@,P

Fairly basic, just defines a function that performs a primality test

Built-in, 1 byte

P

As functions and main code use both different memory models and different commands, this only works in function mode and so would be invalid.

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

cQuents, 3 bytes

?pz

Try it online!

Explanation

?     Mode ? (query)
 p    Builtin: next prime after parameter
  z   Previous item in sequence
   )  Implicit closing parenthesis
      

Query mode returns true if the input is in the sequence, and false if it is not.

\$\endgroup\$
1
  • \$\begingroup\$ Note current version uses Z instead of z \$\endgroup\$
    – Stephen
    Feb 1, 2019 at 4:53
1
\$\begingroup\$

TI-BASIC, 37 bytes

Prompt N
N=1
For(A,2,√(N
Ans+not(fPart(N/A
End
not(Ans

Prompts for N and displays 1 if N is prime or 0 otherwise.

Also in TI-BASIC:

\$\endgroup\$
2
  • 1
    \$\begingroup\$ I rewrote it. This would have done better as a comment as well. \$\endgroup\$
    – Zenohm
    Sep 13, 2015 at 20:19
  • \$\begingroup\$ Nice. I modified my answer. Incidentally, I would have commented on your post but I created this account just to contribute this and didn't have enough reputation to comment. \$\endgroup\$
    – Jakob
    Sep 13, 2015 at 21:40
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\$
6
  • \$\begingroup\$ I'm assuming nspire doesn't allow unclosed parentheses? \$\endgroup\$
    – Adalynn
    Aug 24, 2017 at 0:24
  • \$\begingroup\$ Yeah, it autocloses them. \$\endgroup\$
    – user50198
    Aug 24, 2017 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\$ Aug 24, 2017 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, 2017 at 0:39
  • \$\begingroup\$ If it autocloses them, then isPrime(n should work. \$\endgroup\$
    – Adalynn
    Aug 24, 2017 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\$
2
  • \$\begingroup\$ No need to subtract from zero, as _ performs negation. \$\endgroup\$
    – Dennis
    Sep 6, 2017 at 3:53
  • \$\begingroup\$ @Dennis I tried that earlier, it didn't seem to work... \$\endgroup\$
    – Stan Strum
    Sep 6, 2017 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\$
2
  • \$\begingroup\$ @JonathanFrech No. \$\endgroup\$
    – 0WJYxW9FMN
    Sep 22, 2017 at 21:15
  • \$\begingroup\$ @JonathanFrech The author of this problem asked for a full program. \$\endgroup\$
    – 0WJYxW9FMN
    Sep 23, 2017 at 17:47
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\$
1
  • \$\begingroup\$ Welcome to Programming Puzzles & Code Golf! \$\endgroup\$
    – Dennis
    Sep 26, 2015 at 1:44
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\$
4
  • 2
    \$\begingroup\$ Can you just submit isprime as a function submission? \$\endgroup\$ Dec 9, 2017 at 18:07
  • \$\begingroup\$ i suppose so? good point \$\endgroup\$ Dec 10, 2017 at 4:32
  • 3
    \$\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\$ Dec 12, 2017 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, 2017 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\$

Broccoli, 107 bytes

(fn p ($a) (:= $d 0) (for $i in (range 2 $a) (if (= $a (* $i (int (/ $a $i)))) (:= $d (+ $d 1)))) (= $d 1))

With whitespace added:

(fn p ($a)
    (:= $d 0)
    (for $i in (range 2 $a)
        (if (= $a (* $i (int (/ $a $i))))
            (:= $d (+ $d 1))
        )
    )
    (= $d 1)
)
(map p (range 1 20))

This language is a bit of a pain to work with:

  • You can't take input.

  • You can't define a function from within a function.

  • You can't pass a lambda to a map or reduce or a filter.

  • There is no modulo function.

I'm sure this could be shorter somehow, but I'm just not seeing it.

\$\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
7 8
9
10 11
13

Your Answer

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

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