Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Write a program or function in any language that tells if the input is a prime number.

  • The input is a string representing a natural number in base-10.
  • The output is one of the two strings "Prime" or "Not!!" which correctly identifies the input.
  • Arithmetic operators, bit-wise operators, numeric variables and constants, "math-stuff" in general, etc... are not allowed anywhere in your program. You should use string operations to do all necessary "calculations".
  • You can compare string lengths (which are numbers) - but -10 to your score if you don't.
  • Your program should work on any length input (given enough memory and time).
  • Lowest byte count (UTF-8) wins.
share|improve this question
    
What are the bounds on the number? Can it be negative? Zero? Can it contain a decimal point? –  Quincunx Feb 14 at 23:05
    
If it has bonus points, it isn't code-golf –  Peter Taylor Feb 14 at 23:12
    
Added "natural" to specify bounds on the input. –  Wally Feb 14 at 23:20
    
I was hoping to get surprised with some crazy explicit string manipulation (I was personally thinking about writing code to "decrement" a string so I could loop - and I was torn between string long division and repeated string subtraction...), instead I was surprised with that cool little regex unary prime matcher! Perhaps I need to ask the question again disallowing regex to see if I get even more wonderful stuff? But I don't think anything will be able to come close to the brevity of that regex. –  Wally Feb 15 at 4:02
    
To get "more wonderfull stuff" maybe you could try making it a popularity-contest. Changing the question itself is generally frowned upon though. And I'm not sure you should make a new question or change anything just because someone came up with something that you didn't think of -- I think that happens quite often here. Also, rule bending is part of the sport :) –  daniero Feb 15 at 4:14
add comment

8 Answers

up vote 5 down vote accepted

Ruby, 64 - 10 = 54

puts ('1
'..gets).map{?1}*''=~/^1?$|^(11+?)\1+$/?'Not!!': :Prime

This iterates from the string '1' (plus a newline) to the input string, using Ruby's built in string iteration method which looks an awful lot like adding 1, but which doesn't technically create a high-level numeric variable at any point. It uses the fact that there will be n iterations for an input of n to create an n-length string, then uses a regular expression to determine if that string can be grouped into identical substrings.

share|improve this answer
    
Is the "1" in the "map{?1}" a Fixnum? - if so, you might have to change it to "map('1')? I can't find any documentation on the expression ?1 except some hints that in older versions of Ruby it returned ASCII codes and now it returns a string. –  Wally Feb 15 at 4:36
    
?1 is the same as '1', it's a 1-character string literal. I could replace all instances of 1 but the first with any other character. –  histocrat Feb 15 at 13:12
    
Ok - I just couldn't find that construction well described anywhere! –  Wally Feb 16 at 1:00
    
I choose this as "the winner" since it goes out of the way to avoid even a hint of mathematics. –  Wally Feb 20 at 14:58
    
No hat tip to Abigail? For shame. This is afaict a straight port of the 1998 perl solution: catonmat.net/blog/perl-regex-that-matches-prime-numbers –  skibrianski yesterday
add comment

Ruby: 52 - 10 = 42

Using a variation of that famous prime-matching regex.

puts ?_*gets.to_i=~/^(_|(__+?)\2+)$/?"Not!!":"Prime"

Just to be clear: ?_*gets.to_i is a string operation that appends "_" to itself n times, where n is the input number. As I see it no string lengths are compared, so that should satisfiy the 10 character bonus criterium.

share|improve this answer
1  
+1 because your score is 42. –  Quincunx Feb 14 at 23:06
1  
I'm not that familiar with Ruby, so correct me if I'm wrong, but doesn't the "to_i" convert the string to an integer? Not that I don't love the brillient prime checker in unary… –  Wally Feb 15 at 3:22
1  
@Wally I don't think "convert" is not the right word, but the method returns an int, yes. Still, I don't use any of the following Arithmetic operators, bit-wise operators, numeric variables and constants, and you can't really classify calling a method as "math-stuff" in general..? –  daniero Feb 15 at 4:06
    
@daniero Sounds reasonable - perhaps right at the edge of the spec. –  Wally Feb 16 at 0:59
add comment

Perl 52-10=42

Implementation

print((('-'x$ARGV[0])=~/^.$|^(..+?)\1+$/)?Not:Prime)

Demo

$ seq 1 10|xargs -I{} bash -c "echo -n '{} '  && perl Prime.pl {} && echo"
1 Not
2 Prime
3 Prime
4 Not
5 Prime
6 Not
7 Prime
8 Not
9 Not
10 Not
share|improve this answer
4  
1 isn't really a prime. –  Ed Cottrell Feb 15 at 16:26
    
Uses a numerical array index - so at the edge of the spec. –  Wally Feb 20 at 14:56
    
Use pop instead of $ARGV[0], save 4 chars, remove numerical array index –  mob yesterday
add comment

ECMAScript 6, 159 - 10 = 149

Sounds like a task for regex. I/O with prompt/alert as usual.

for(s=prompt(u=""); /[^0]/.test(s); )
  s=s.replace(/(.)(0*)$/,(_,d,t)=>u+="x"," 012345678"[d]+t.replace(/0/g,"9"))
alert(/^((xx+)\2+|x?)$/.test(u)?"Not!!":"Prime")

The while loop decrements the decimal number by one each iteration purely by regex. The final regex matches a string consisting of a composite number of x's, by first matching one factor, then another by repeating the first factor one for the rest of the string.

share|improve this answer
    
I like the string decrement function - clear and concise. –  Wally Feb 20 at 14:36
add comment

Javascript 266

function N(a){function b(a){return P.every(function(b){if(n=b,i=a.length,j=b.length,j>i) return;if(j==i) return 1;while(n.length<i)n+=b;return n.length!=i})}if(q=A,A!=a)for(;q.length.toString()!=a;)b(q)&&P.push(q),q+=A;console.log(b(q)?"Prime":"Not!!")}A="0",P=[A+A]

Creates a function called N which will print the desired result. The unminified version looks like this. I did a hand minify to clean up some variables and then ran that through uglify and then hand minified that again.

// A a string of "0" for using to generate long strings
// P is the store for all known primes
A="0", P=[A+A];
function N(val) {
  function _isPrime(str) {
    // go through all the known primes and return true
    // if we don't match on any of them
    return P.every(function(prime) {
      // prime is some known string whose length is a prime number
      tsr = prime, strlen = str.length, primelen = prime.length;
      // if the string we're checking has fewer chars than
      // this then it's not a prime
      if(strlen < primelen) return 0;
      // if the string we're checking has the same number of chars
      // as the the prime we're checking against then it is a prime
      if(primelen == strlen) return 1;
      // Keep incrementing our temporary string with the prime we're
      // checking. we'll break out of the loop once the temporary string
      // is greater than or equal to the string we're testing
      while(tsr.length < strlen) {
        tsr += prime;
      }
      return !(tsr.length == strlen)
    });
  }
  // start with a string of one unit
  nstr = A
  if(A!=val) {
    // keep incrementing the string so that we can compile a list
    // of known primes smaller than this value
    while(nstr.length.toString() !== val) {
      if(_isPrime(nstr)) {
        P.push(nstr);
      }
      nstr += A;
    }
  }
  console.log(_isPrime(nstr) ? "Prime" : "Not!!");
}

Tested it using this snippet:

for(var X=0;X<10;X++) {
  console.log('checking: ' + X);
  N(X.toString());
}
share|improve this answer
1  
I'm not sure I see how this works, but I do see a numeric variable (i) and an arithmetic operator (i++). –  Wally Feb 16 at 1:05
    
Oh, didn't realise that I couldn't do a for loop like that.. will rewrite it tonight. –  Sugendran Feb 19 at 8:20
    
Basically I'm producing an array of strings whose lengths are primes. So when I get an input I keep adding characters to a string until the length value for the string matches the input. I then take this string and see if I can evenly divide it by any of the known primes. If I can't then it must be a prime. And by divide I mean I take the known prime string and keep adding it to itself the the length of the string is either equal to or larger than the string in question. –  Sugendran Feb 19 at 8:23
    
I've updated the code, it actually reduces the number of chars slightly :) –  Sugendran Feb 19 at 21:55
    
Cool. It looks like the same idea as the regex, but more efficient and explicitly showing the actual logic. –  Wally Feb 20 at 14:26
add comment

Bash 66 - 10 = 56

Implementation

[[ -z `printf %$1s|grep -P "^(..+?)\1+$"` ]]&&echo Prime||echo Not

Demo

$ seq 1 10|xargs -I{} bash -c "echo -n '{} '  && ./Prime.sh {}"
1 Prime
2 Prime
3 Prime
4 Not
5 Prime
6 Not
7 Prime
8 Not
9 Not
10 Not
share|improve this answer
    
As above, 1 is not prime. –  Wally Feb 20 at 14:34
add comment

GolfScript 49 - 10 = 39 (?)

I'm not too sure if this actually follows the rules... but it will work for any input greater than 0.

~,.);{{;n}%:a{);.a\%!!}do);}{}if!"Prime""Not!!"if

This works essentially the same way as all of the ^.?$|^(..+?)\1+$ regex answers.

This does however use numbers in order to translate the given number into an array of \n strings the size of that number but so does the leading Ruby answer. Also I probably missed a bunch of length optimizations since this is my first attempt at using GolfScript.

Rough translation using variables instead of stack :

function IsPrime (var input)
    var is_prime

    // in the GolfScript version no such variable is 
    // actually created and the number is just pushed 
    // onto the stack instead
    var input_as_int = stringToInt( input )
    arr array = newArrayOfLength( input_as_int )

    // this is a side effect of the "," function
    // but none of the numbers here are actually used
    for i in 0..lengthOf( array )
        setElementAtIndex( array, i, i )
    end for

    arr copy = copyArray( array )
    removeLastElementOf( copy )

    // this will be only true if the input was 1
    if copy is empty
        is_prime = false
    else
        arr array_of_newlines = emptyArray()

        // make a new array of the same size but filled with
        // newline characters instead of numbers
        for each element of array
            addToArray( array_of_newlines, '\n' )
        end for

        arr divisor = copyArray( array_of_newlines )

        label "loop"
            // decrement divisor
            removeLastElementOf( divisor )
            arr remainder = removeEveryOccurenceOfFirstArrInSecondArr( 
                                                   divisor,
                                                   array_of_newlines )

            // if this is false then the current divisor
            // is a factor of the input. If there are no
            // prime factors then this will still eventually 
            // be false when the divisor reaches 1
            // which would mean that the input is prime
            if remainder is not empty
                goto "loop"
            end if
        end "loop"

        removeLastElementOf( divisor )
        // now the divisor will be empty only if it was 1
        // in which case the input must have been prime
        is_prime = divisor is empty
    end if

    if is_prime
        print "Prime"
    else
        print "Not!!"
    end if

end function
share|improve this answer
    
Love the brevity, but I have to agree that it does bend the rules a bit much - pushing a number onto the stack is, IMO, the same as using a numeric variable. –  Wally Feb 20 at 14:39
add comment

Python 3, 109-10 = 89

print(['Not','Prime'][(lambda i:not any(' '*i==(' '*u)*v for u in range(i)for v in range(i)))(int(input()])

Not comparing string lengths, but string inclusion. Cross posted from duplicate Determine if a number is prime without using arithmetic

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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