-1
\$\begingroup\$

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.

\$\endgroup\$

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
2
\$\begingroup\$

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".
\$\endgroup\$
1
\$\begingroup\$

Pyth - 25 23 bytes

Heavily golfable, uses filter.

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

Test Suite.

\$\endgroup\$
1
\$\begingroup\$

Pyth, 22 bytes

+*}0%LQr2Q"not ""prime

Try it online.

\$\endgroup\$
1
\$\begingroup\$

Python 2, 59

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

Thanks Alex! One day I will remember.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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")
\$\endgroup\$

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