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.

  • \$\begingroup\$ Define inefficient. Is O(n) inefficient enough? Or do you just mean by following your specific algorithm? \$\endgroup\$
    – Justin
    Commented Sep 17, 2015 at 3:35
  • \$\begingroup\$ The specific algorithm of iterating from 2 to n-1. \$\endgroup\$
    – Arcturus
    Commented Sep 17, 2015 at 3:37
  • 5
    \$\begingroup\$ Naïve implementations of Wilson's Theorem are a lot less efficient... \$\endgroup\$
    – Dennis
    Commented Sep 17, 2015 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
    Commented Sep 17, 2015 at 4:01

6 Answers 6


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.