218
\$\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
3 4
5
6 7
11
2
\$\begingroup\$

K, 25 bytes

`0:$~x!1+*/1+!(x:. 0:`)-1
\$\endgroup\$
1
  • 1
    \$\begingroup\$ How should this be run? I tried kona/k program <<< input, but that doesn't seem to work. \$\endgroup\$ – Dennis Sep 11 '15 at 19:00
2
\$\begingroup\$

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

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

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

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

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

Python 2, 46 65 52 51 bytes

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

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

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

Example Runs

I ran this in IPython:

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

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

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

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

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

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

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

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

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

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

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

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

Fortran 90, 208 bytes

program a
integer::n,i
logical::p
read(*,*)n
if(n==2) then
p=.true.
else if(n<2 .or. mod(n,2)<1) then
p=.false.
else
p=.true.
do i=3,n-1,2
if(mod(n,i)<1) then
p=.false.
exit
endif
enddo
endif
write(*,*)p
end

This uses trial division. Not a whole lot has been golfed here beyond removing spaces. Here it is with spaces for readability:

program primes
    integer :: n, i
    logical :: p

    ! Read n from STDIN
    read (*,*) n

    if (n == 2) then
        p = .true.
    else if (n < 2 .or. mod(n, 2) == 0) then
        p = .false.
    else
        p = .true.
        do i = 3, n-1, 2
            if (mod(n, i) == 0) then
                p = .false.
                exit
            endif
        enddo
    endif

    ! Write a logical to STDOUT
    write (*,*) p
end program
\$\endgroup\$
2
  • \$\begingroup\$ Surely need a space before then? \$\endgroup\$ – Erik the Outgolfer Jul 17 '16 at 15:49
  • \$\begingroup\$ @EʀɪᴋᴛʜᴇGᴏʟғᴇʀ Unfortunately yes. \$\endgroup\$ – Alex A. Jul 17 '16 at 16:13
2
\$\begingroup\$

APL, 13 bytes

2=0+.=X|⍨⍳X←⎕

Inefficient, but it works. A number is a prime if it is only evenly divisible by 1 and itself, so it just tests all of these. Output is 0 or 1.

Explanation:

          X←⎕  ⍝ read a number, store it in X
      X|⍨⍳      ⍝ X mod [1..X]
  0+.=          ⍝ count the 0s
2=              ⍝ are there 2? 
\$\endgroup\$
0
2
\$\begingroup\$

Lua, 71 67 bytes

n=io.read"*n"for i=2,n-1 do if n%i==0 then r=1 end end print(not r)

Ungolfed:

n=io.read"*n"
for i=2,n-1 do
    if n%i==0 then 
        r=1 
    end 
end 
print(not r)

This program just uses trial division to find if a number is prime or not.

3 bytes saved thanks to @Ruth Franklin

\$\endgroup\$
3
  • \$\begingroup\$ You can save a couple of bytes by using r=1 instead of r=true (as not 1 is false anyway) \$\endgroup\$ – Ruth Franklin Sep 13 '15 at 13:24
  • \$\begingroup\$ Ah okay, thanks for the tip :) \$\endgroup\$ – Nikolai97 Sep 13 '15 at 17:15
  • \$\begingroup\$ Inputs less than 2 (1, 0, and negative numbers) all return true. \$\endgroup\$ – ECS Jan 25 '16 at 8:33
2
\$\begingroup\$

Perl, 38 or 47 bytes

use ntheory":all";say is_prime(shift);

Prints 0 if composite, 2 if definitely prime, 1 if a probable prime. The results for all 64-bit inputs are deterministic. With 0.53+ this extends to 82-bit inputs. It's also sometimes done for up to 200-bit inputs (special form or very easy proof). The probable prime test is an extra-strong BPSW test followed by 1-5 random-base Miller-Rabin tests.

use ntheory":all";say is_provable_prime(shift);

Uses BLS75-T5 or ECPP to prove the result. Deterministic for all inputs. Very fast to ~500 digits, works pretty well to 1000 or so digits.

This is included in Strawberry Perl for Windows. Certainly using a module is iffy under the golfing loopholes, but this is a normal module and Perl is all about CPAN. It's also ridiculously faster and more useful than the clever but stupid regex.

\$\endgroup\$
5
  • \$\begingroup\$ What does "probably prime" mean? \$\endgroup\$ – ASCIIThenANSI Sep 11 '15 at 19:02
  • 2
    \$\begingroup\$ It means it passed some probabilistic prime test that, very rarely, might give a false positive, and you may optionally want to run a more thorough test. \$\endgroup\$ – Lynn Sep 11 '15 at 19:11
  • \$\begingroup\$ For ntheory, it means it passed an ES BPSW test (that has no counterexamples found in the 35 years since it was introduced) plus one or more extra random-base Miller-Rabin tests. I just added the new result for deterministic M-R testing out to ~82 bits. A bit stronger than Mathematica's PrimeQ function. Primality proofs can be done, but very few people care vs. good probable prime tests. Arguably the chance of failure is smaller than a software or hardware error in the proof code. Not to mention most people want the result for a 2000 digit number in 0.1 seconds instead of 1,5 hours. \$\endgroup\$ – DanaJ Sep 12 '15 at 5:05
  • \$\begingroup\$ The challenge explicitly asks for non-probabilistic solutions. \$\endgroup\$ – Martin Ender Sep 14 '15 at 10:19
  • \$\begingroup\$ @MartinBüttner Adjusted text and also asked the challenge to be more specific about what "deterministic" means. Thanks. \$\endgroup\$ – DanaJ Sep 14 '15 at 11:56
2
\$\begingroup\$

Pharo, 7 bytes

isPrime

Pharo is an open source flavour of Smalltalk, a fork of Squeak. All integer instances understand the message isPrime and will respond with a boolean value. To quickly test this, simply select the text containing the number and the message (e.g. 1 isPrime) and "print-it" (or "inspect-it") from the context menu or via keyboard shortcut.

enter image description here

For anyone interested, here's the implementation of that method on the class Integer:

isPrime
    "Answer true if the receiver is a prime number. See isProbablyPrime for a probabilistic
    implementation that is much faster for large integers, and that is correct to an extremely
    high statistical level of confidence (effectively deterministic)."

    self <= 1 ifTrue: [ ^false ].
    self even ifTrue: [ ^self = 2].
    3 to: self sqrtFloor by: 2 do: [ :each |
        self \\ each = 0 ifTrue: [ ^false ] ].
    ^true

So the receiver of this message first covers the base cases (numbers <= 1 aren't prime, even numbers are only prime if they're 2), then checks each odd number from 3 to the floor of its squareroot to see whether dividing itself by each of those numbers results in a zero remainder. If such a divisor is found, false is returned, otherwise true. As the method comment states, there is also a faster (but probabilistic) implementation.

And just for fun, because Smalltalk is so simple with collections, here's how to get a collection of prime numbers up to 100:

(1 to: 100) select: [:each | each isPrime]

The output would be:

#(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97)
\$\endgroup\$
1
  • \$\begingroup\$ I'm pretty sure (but unable to confirm) that the same method exists in Squeak, and probably several other flavours of Smalltalk. If so, please feel free to update this answer. \$\endgroup\$ – Amos M. Carpenter Sep 15 '15 at 7:57
2
\$\begingroup\$

JavaScript, 50 47 bytes

n=+prompt();for(i=2;n%i&&i*i<n;i++);n<3?n-1:n%i

This is a basic translation of @steveverrill's C answer :)

\$\endgroup\$
8
  • 1
    \$\begingroup\$ "Write a full program that..." \$\endgroup\$ – FryAmTheEggman Sep 11 '15 at 15:10
  • \$\begingroup\$ It is now a full program, and I have attributed you at the bottom of my answer :) \$\endgroup\$ – Sam Sep 11 '15 at 15:15
  • 6
    \$\begingroup\$ I believe you need an alert or something to output from a full program in JS? \$\endgroup\$ – FryAmTheEggman Sep 11 '15 at 15:17
  • 2
    \$\begingroup\$ @FryAmTheEggman I'd say that a web browser's console counts as a standard JS interpreter, and pretty much all consoles output the result. This outputs 0 (which is falsy) if the number is not prime. \$\endgroup\$ – Reinstate Monica -- notmaynard Sep 11 '15 at 16:14
  • \$\begingroup\$ You could save three bytes by getting rid of the 'n' in prompt('n'). I believe moving the i++ into the condition, like so: for(i=2;n%i&&i*i++<n;); would also save a byte. \$\endgroup\$ – ETHproductions Sep 11 '15 at 16:35
2
\$\begingroup\$

Perl 6, 16 bytes

Using built-ins is allowed (even if makes for a boring answer), and this is about shortest solutions, so...

say is-prime get

get obtains a line from STDIN, is-prime when used on string converts input to integer, say outputs the boolean.

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

Common Lisp, 111 88 bytes

(defun p(n c)(cond((= n 1)0)((= n c)1)((eq(rem n c)0)0)(t(p n(1+ c)))))(print(p(read)2))

Try it online!

I'm kinda new to Lisp, so this could probably be improved. It's a very straightforward algorithm.

Ungolfed and commented:

(defun primep (n c)                ; define a function p with args n and c
    (cond                          ; conditional statement similar to switch-case
        ((= 1 n) 0)                ; if n is 1, return 0. Difficult to handle this.
        ((= n c) 1)                ; if c = n, then we have gotten all the way through
                                   ; without finding a single divisor. It's prime; return 1.
        ((eq (rem n c) 0) 0)       ; if n is evenly divisible by c, return 0
        (t (primep n (1+ c)))      ; if all else fails, increment c and recurse
    )
)
(print (primep (read) 2))          ; eval one line from stdin, call primep with an initial
                                   ; count of 2, and print the result
\$\endgroup\$
2
\$\begingroup\$

C,59 bytes

main(i,j){scanf("%d",&i);for(j=2;i%j++;);printf("%d",j>i);}

It outputs 1 if the input is a prime and 0 otherwise.

\$\endgroup\$
1
  • \$\begingroup\$ +1 This very nearly fails for an input of 1, where the for() loop will repeat almost forever. But eventually j will overflow and become negative, and then count back up again towards zero. When j==-1, i%j==0, so the loop exits and the program outputs 0 because 1>-1. This is fortunate because the next iteration would raise a divide-by-zero error. \$\endgroup\$ – r3mainer Oct 13 '15 at 19:04
2
\$\begingroup\$

TeaScript, 5 bytes

$P(x)

Returns true if input is a prime and false of it is a composite number.

Try it online here Does NOT work in Chrome. Input is given in the first field.

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

Carrot (version ^3), 3 bytes

#^P

Basically takes the input (#) and checks if it is a prime number (P) or not.

Note that this program takes the input as a string and,without converting it into a integer, it checks if the number is a prime or not.

Try it online here. Although my programming language has been created after the challenge, it was not created to "abuse" this challenge.

\$\endgroup\$
1
  • \$\begingroup\$ This is scary good. +1 \$\endgroup\$ – Addison Crump Nov 4 '15 at 20:29
2
\$\begingroup\$

Stack, 132 bytes:

'' '' input num `n set 2 `i set { n i % 0 = n 1 = or { 0 print } { i n 2 - gt { 1 print } { i 1 + `i set p } ifelse } ifelse } `p def p

Your basic test every number from 2 to n primality test.

\$\endgroup\$
2
  • \$\begingroup\$ Unnecessary whitespace is unnecessary? '' input num `n set 2 `i set { n i % 0 = n 1 = or { 0 print } { i n 2 - gt { 1 print } { i 1 + `i set p } ifelse } ifelse } `p def p saves 10 bytes \$\endgroup\$ – Florrie Nov 6 '15 at 17:00
  • \$\begingroup\$ @towerofnix thanks \$\endgroup\$ – BookOwl Nov 7 '15 at 15:49
2
\$\begingroup\$

Minkolang, 29 5 bytes

I have since added a built-in for primality testing (it uses a parallelized version of the Sieve of Sundaram).

n2MN.

Explanation

n     Take integer from input
2M    Push 1 if prime, 0 otherwise
N.    Output as integer and stop.

Old version (does not use a built-in):

This was surprisingly long. I'll probably implement a built-in for this (since primality checking will probably be useful elsewhere).

nd2`4&1-N.d2-[0ci2+%3&0N.]1N.

Explanation

n                                Take integer as input.
 d2`4&1-N.                       Output 0 if 1, 1 if 2.
          d2-[           ]       Trial division loop.
              0ci2+%             Check to see if it's divisible by <loop counter>.
                    3&0N.        If so, output 0 and stop.
                          1N.    It's prime! Output 1 and stop.
\$\endgroup\$
2
\$\begingroup\$

pl, 1 byte

Try it online.

At the moment, pl uses a lazy trial division builtin. I'll replace it with something that doesn't suck later.

\$\endgroup\$
3
  • \$\begingroup\$ Is that really one byte? I count three but I'm not sure what the rules are. \$\endgroup\$ – histocrat Dec 21 '15 at 16:56
  • \$\begingroup\$ pl uses CP437 as its encoding. This char is one byte (0xF0) in it. \$\endgroup\$ – a spaghetto Dec 21 '15 at 16:57
  • \$\begingroup\$ And now I know a thing. Thank you! \$\endgroup\$ – histocrat Dec 21 '15 at 17:08
2
\$\begingroup\$

ROOP, 17 bytes

I
w#H

 P
  w
  O

The w operator reads a number from the keyboard because it has an input object above (I). The input object moves to the right and the number created falls down. The P operator checks whether the number is prime and places a 1 or a 0 on the right (eliminating the number). Then the input object is moved to the right, the number created can not move anywhere. The operator H is activated because it has a object above and terminates the program at the end of all operators. The operator w, puts the number 1 or 0 in the display.

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

jq, 38 bytes

. as$n|[range(2;.)]|all($n%.>0)and$n>1

Sample run:

bash-4.3$ jq '. as$n|[range(2;.)]|all($n%.>0)and$n>1' <<< 2015
false

On-line test:

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

F#, 99 88 bytes

[<EntryPoint>]
let f a= 
 let i=int a.[0]
 Seq.forall((%)i>>(<)0)[2..i-1]|>printfn"%b";0

Explanation of the interesting part:

                      [2..i-1]              // Generate a list of possible divisors (from 2 to i-1) - for 2, this is an empty list.
Seq.forall(          )                      // Check if none of them are actual divisors, that is
           (%)i>>(<)0                           // That i % it is greater than 0. This is equivalent to (fun d -> i % d > 0)
                              |>printfn"%b" // And print the answer as a boolean

Update: Turns out, the entry point doesn't have to be called "main", and the argument array doesn't have to be called "argv"! =)

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

Oracle SQL 11.2, 73 bytes

SELECT SUM(DECODE(MOD(:1,LEVEL),0,1,0))-2 FROM DUAL CONNECT BY LEVEL<=:1;

Return 0 if prime, any other value is false

\$\endgroup\$
1
  • \$\begingroup\$ A slightly smaller version SELECT MIN(MOD(:1,LEVEL+1))FROM DUAL CONNECT BY LEVEL<:1-1; that will return 0 or 1 \$\endgroup\$ – MickyT Apr 10 '16 at 21:37
2
\$\begingroup\$

Reng v.1, 36 39 bytes

This tests if the input is a prime. (+3 bytes because I forgot to check if input = 1)

i:11#x   eqv0n~
x1+#x:x,?v$\
    ~nex$/

All because I forgot to implement member switching. I am rather proud of this, however, because it uses an interesting feature of Reng: you can redefine any character's meaning. In this case, we see constant redefinition.

i takes input, and 1 pushes 1. We also define x as 1 (1#x) and print zero and terminate if the input is 1 (eqv0n~). Then, the pointer is directed to the next line, x1+#x:x,?v$\. (The last character is a NOP for this instance.)

For the first iteration, 1+ increments x, yielding 2. This is where our trial division starts. #x defines x to be the top element of the stack, in this case, 2. : duplicates the TOS, the input element, and x puts down its value, 2 in this case. , is the modulus operator, and yields i % x. If this is zero, we are directed downwards by v. Otherwise, we drop the modulus and redo the line again.

When we are directed downward by v, we meet / which executes the line ~nex$, equivalent in a left-to-right form to $xen~. $ drops a value, x lays down x, and e checks for equality. If they are equal (in the case that x is the input), this is 1. Otherwise, this is 0.

Test cases

The programs pictured are still valid, but fail to handle 1 correctly, unlike the program above.

Is 5 a prime?

Yes!

Yes.

Is 169 a prime?

No!

No.

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

VHDL, 236 bytes

entity e is
port(n:natural;b:out bit);end;architecture a of e is
function p(n:natural)return bit is
begin
if n=1 then
return'0';end if;for i in 2 to n-1 loop
if n mod i=0 then
return'0';end if;end loop;return'1';end;begin
b<=p(n);end a;

The input n is an input port of the entity e; a natural number (starts at 0 for VHDL). b is an output port of entity e; a bit (meaning '1' or '0'). This works by the ever-famous method of trial division, with a special case for 1. This is what it looks like formatted nicely:

entity e is
    port(   n : in natural;
            b : out bit);
end;

architecture a of e is
    function p(n:natural) return bit is
    begin
      if n=1 then
          return '0';
      end if;
      for i in 2 to n-1 loop
          if n mod i=0 then
              return '0';
          end if;
      end loop;
      return'1';
    end;
begin
    b<=p(n);
end a;

Here's the testbench I used for verification:

entity m is
end;

architecture a of m is
    signal i_n : natural := 2;
    signal i_b : bit;

    type int_vector is array(natural range<>) of natural;

    constant primes : int_vector := (2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97);

    function is_prime(n : natural) return boolean is
    begin
        for i in primes'range loop
            if n=primes(i) then
                return true;
            end if;
        end loop;
        return false;
    end;
begin
    x:entity work.e port map(n=>i_n, b=>i_b);
    process
    begin
        for i in 1 to primes'right loop
            i_n <= i;
            wait for 10 ns;
            if is_prime(i) then
                assert i_b='1';
            else
                assert i_b='0';
            end if;
        end loop;
        report "finished" severity error; -- error to stop simulation
    end process;
end a;

This is the result.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ @ais523 except the question specifies that it must be a full program \$\endgroup\$ – Justin May 11 '17 at 16:30
2
\$\begingroup\$

Labyrinth, 21 bytes

?
:
}()"{
{: *}{:*{%!

Terminates with an error, with the error message going to STDERR.

Try it online!

Explanation

This uses the same approach based on Wilson's theorem as Sp3000's answer, but I managed to decompose his 3x3 loop into two 2x2 loops which is generally better for golfing Labyrinth.

Labyrinth primer:

  • Labyrinth has two stacks of arbitrary-precision integers, main and aux(iliary), which are initially filled with an (implicit) infinite amount of zeros.
  • The source code resembles a maze, where the instruction pointer (IP) follows corridors when it can (even around corners). The code starts at the first valid character in reading order, i.e. in the top left corner in this case. When the IP comes to any form of junction (i.e. several adjacent cells in addition to the one it came from), it will pick a direction based on the top of the main stack. The basic rules are: turn left when negative, keep going ahead when zero, turn right when positive. And when one of these is not possible because there's a wall, then the IP will take the opposite direction. The IP also turns around when hitting dead ends.

Now we can look at the code. The program starts with a short linear (vertical) bit:

?   Read input N as an integer and push onto main.
:   Duplicate N.
}   Move one copy over to aux.

The IP is now at a junction, and in fact the small 2x2 block acts as a loop which is traversed in clockwise order:

(   Decrement N. If it hits zero, we exit the loop.
:   Duplicate N.
{}  Move a value over from aux and push it back. Together this does nothing.

So this loop leaves all the numbers from N-1 down to 0 on the main stack. Now there's the single ), which increments that 0 back up to 1, such that all the non-zero numbers on top of the stack will multiply together to (N-1)! (including the special case of 0! == 1).

The next 2x2 block is a loop which performs this multiplication and its traversed in counter-clockwise order. The tricky part is that we need to check the value below the product to see if we're done, otherwise we'd end up losing the product by multiplying it with an implicit 0 below.

"   No-op, does nothing.
*   Multiply the top two values on main.
}   Move the product over to aux, exposing the value below. If that's zero,
    we exit the loop.
{   Pull the product back onto main for the next iteration.

Now the main stack is empty and the aux stack contains (N-1)! on top of N. Time to wrap things up:

{   Pull (N-1)! over from aux.
:*  Duplicate and multiply, squaring the factorial.
{   Pull N over from aux.
%   Take modulo, computing (N-1)!^2 % N.
!   Output the result.

Now the IP hits a dead end and has to turn around. The next thing it tries to execute is % but that would now attempt to compute 0 % 0 which terminates with a division-by-zero error.

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

Fuzzy Octo Guacamole, 21 bytes

^-!.1C[d2ss.p*.+]s.Zm

Outputs 0 for false, 1 for true. Thanks to @xnor for the algorithm.

Explanation:

^-!.1C[d2ss.p*.+]s.Zm
^                      # Get Input
 -                     # Decrement
  !                    # Set for-loop counter
   .                   # Swap stacks
    1C                 # Set both stacks to [1].  (push 1 and copy to other stack)
      [         ]      # For loop for duration of input - 1
       d2              # Duplicate the top of stack and push 2 after
         ss            # Put them on the other stack, in reverse order.
           .           # Switches stacks
            p          # Power function. x^y (ToS^2)
             *         # Multiply
              .+       # Move back to the other stack and increment
                ]      # (repeat)
                 s.    # Move the ToS over and go with it
                   Z   # Reverse the stack.
                    m  # Modulus, x%y.
                       # (implicit output)

We start with each stack having 1. Let the bottom of one stack be n, the other bottom be P. We multiply P by n^2, and then increment n. Do this n-1 times. Then take P%n.

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

WistfulC, 381 bytes

if only int n were 0...
wish for "%d", &n upon a star
if n < 2 were true...
    wish "not prime" upon a star
    if wishes were horses...
*sigh*
if only int i were 2...
someday i will be n...
    if n % i were 0...
        wish "not prime" upon a star
        if wishes were horses...
    *sigh*
    if only i were i + 1...
*sigh*
wish "prime" upon a star
if wishes were horses...

Outputs prime if prime, not prime if not prime.

I went for entertainment value more than small size. Here's a golfed, (arguably) less funny version (286 bytes):

if only int n were 0...wish for "%d",&n upon a star
if n<2...wish "0" upon a star
if wishes were horses...*sigh*if only int i were 2...someday i==n...if !(n%i)...wish "0" upon a star
if wishes were horses...*sigh*if only i were i+1...*sigh*wish "1" upon a star
if wishes were horses...
\$\endgroup\$
1
  • \$\begingroup\$ You can save some bytes by return truthy/falsy values? \$\endgroup\$ – Rɪᴋᴇʀ Jul 21 '16 at 17:55
2
\$\begingroup\$

Sesos, 40 39 bytes

0000000: 16f0be afcf9c 37fcfe 8c19d7 c671d7 668ee3 f57b33  ......7......q.f...{3
0000015: 877bc6 662edb b961ba 8763bc 666e3c 66ec01         .{.f...a..c.fn<f..

Try it online! Check Debug to see the generated binary code.

Background

To identify primes, we use a corollary of Wilson's theorem:

corollary of Wilson's theorem

How it works (WIP)

The binary file above has been generated by assembling the following SASM code.

set numin
set numout

get
jmp
    jmp, fwd 1, add 1, fwd 1, add 1, fwd 1, add 1, rwd 3, sub 1, jnz
    fwd 1, sub 1, fwd 2
    jmp, rwd 3, add 1, fwd 3, sub 1, jnz
    rwd 1, sub 1
jnz
rwd 1, add 1, rwd 2
jmp
    fwd 1
    jmp, fwd 2, add 1, rwd 2, sub 1, jnz
    fwd 1
    jmp
        fwd 1
        jmp, fwd 1, add 1, rwd 3, add 1, fwd 2, sub 1, jnz
        fwd 1
        jmp, rwd 1, add 1, fwd 1, sub 1, jnz
        rwd 2
        sub 1
    jnz
    fwd 1
    get
    rwd 4
jnz
fwd 2
jmp
    rwd 1, sub 1, rwd 1, add 1, fwd 1
    jmp, rwd 1, jnz
    rwd 1
    jmp, fwd 1, add 1, rwd 1, sub 1, jnz
    fwd 2
    jmp, fwd 1, jnz
    rwd 1, sub 1
jnz
rwd 2
put
\$\endgroup\$
2
\$\begingroup\$

Idris, 78 bytes

main:IO()
main=let S n=length!getLine in print$0<(pow(product[1..n])2`mod`S n)

This takes input as a unary string (it uses the string length as input).

Compile this with idris -O3 or you’ll spend forever in Nat-computey hell.

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

CASIO-BASIC, 28 bytes

?->A:For 2->B To A:A Rmdr B=0=>B->A:Next

This prompts for a number, then outputs the number if it is prime, else zero.

I'm not really sure how this works. I originally thought it would output the value from the last assignment (stored in Ans), but then it would output the lowest factor of the number, not zero.

Note: -> and => are ASCII representations of one symbol each (the assign-to and conditional operators).

The size was calculated as the size of this program (60 bytes) minus the size of an empty program (32 bytes).

\$\endgroup\$
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
1
3 4
5
6 7
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.