Primes, as efficiently inefficient as possible [duplicate]

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

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

CJam, 25 bytes

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


Try it online

Explanation:

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.
"prime"
Push "prime".


Pyth - 25 23 bytes

Heavily golfable, uses filter.

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


Pyth, 22 bytes

+*}0%LQr2Q"not ""prime


Try it online.

Python 2, 59

i=input()
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)

n=input();x=0
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="")


Ungolfed:

# Read n from STDIN
n <- scan()

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