This question already has an answer here:

Write a program that tests if a number n is prime by checking that none of the integers between 2 and n-1 (inclusive) divide n (you must use this algorithm!). The input to STDIN should be an integer n (strictly) greater than 1. The output to STDOUT should be prime if n is prime and not prime if n is not prime.

Even though you are intentionally writing an inefficient program, this is still code golf, fellas. Standard CG rules apply. Shortest code in bytes wins.


marked as duplicate by Geobits, Justin, Alex A. Sep 17 '15 at 4:10

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • \$\begingroup\$ Define inefficient. Is O(n) inefficient enough? Or do you just mean by following your specific algorithm? \$\endgroup\$ – Justin Sep 17 '15 at 3:35
  • \$\begingroup\$ The specific algorithm of iterating from 2 to n-1. \$\endgroup\$ – Arcturus Sep 17 '15 at 3:37
  • 5
    \$\begingroup\$ Naïve implementations of Wilson's Theorem are a lot less efficient... \$\endgroup\$ – Dennis Sep 17 '15 at 3:41
  • 4
    \$\begingroup\$ There are already many answers on this question that use this method (or one with very trivial changes). \$\endgroup\$ – Geobits Sep 17 '15 at 4:01

CJam, 25 bytes

li_,2>f%:*!"not "*"prime"

Try it online


li    Get input and convert to integer.
_,    Create range [0 ... n-1].
2>    Slice off first two elements, to get [2 ... n-1].
f%    Apply modulo with all range members to input.
:*    Calculate product of the results. This will be 0 if one of the modulo
      results was 0, non-zero if the input is prime.
!     Negate. We now have 0 for primes, 1 for non-primes.
"not "*
      Push "not " 0/1 times based on value.
      Push "prime".

Pyth - 25 23 bytes

Heavily golfable, uses filter.

+?f!%QTr2Q"not "k"prime

Test Suite.


Pyth, 22 bytes

+*}0%LQr2Q"not ""prime

Try it online.


Python 2, 59

print"not "*any(i%n<1for n in range(2,i))+"prime"

Thanks Alex! One day I will remember.


Python 2, way too many bytes (95, to be exact)

for i in range(2,n):
 if n%i==0:x+=1;print'not prime';break
if x==0:print'prime'

Heavily golfable for sure.


R, 59 bytes

n=scan();cat(if(n>2&sum(!n%%2:(n-1)))"not ","prime",sep="")


# Read n from STDIN
n <- scan()

# Test primality and write to STDOUT
if (n > 2 & sum(!(n %% 2:(n-1)))
    cat("not prime")

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