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.

• Define inefficient. Is O(n) inefficient enough? Or do you just mean by following your specific algorithm? Sep 17, 2015 at 3:35
• The specific algorithm of iterating from 2 to n-1. Sep 17, 2015 at 3:37
• Naïve implementations of Wilson's Theorem are a lot less efficient... Sep 17, 2015 at 3:41
• There are already many answers on this question that use this method (or one with very trivial changes). Sep 17, 2015 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: