14
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ What are the bounds on the number? Can it be negative? Zero? Can it contain a decimal point? \$\endgroup\$ – Justin Feb 14 '14 at 23:05
  • \$\begingroup\$ If it has bonus points, it isn't code-golf \$\endgroup\$ – Peter Taylor Feb 14 '14 at 23:12
  • \$\begingroup\$ Added "natural" to specify bounds on the input. \$\endgroup\$ – Wally Feb 14 '14 at 23:20
  • \$\begingroup\$ 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. \$\endgroup\$ – Wally Feb 15 '14 at 4:02
  • \$\begingroup\$ 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 :) \$\endgroup\$ – daniero Feb 15 '14 at 4:14
7
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Wally Feb 15 '14 at 4:36
  • \$\begingroup\$ ?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. \$\endgroup\$ – histocrat Feb 15 '14 at 13:12
  • \$\begingroup\$ Ok - I just couldn't find that construction well described anywhere! \$\endgroup\$ – Wally Feb 16 '14 at 1:00
  • \$\begingroup\$ I choose this as "the winner" since it goes out of the way to avoid even a hint of mathematics. \$\endgroup\$ – Wally Feb 20 '14 at 14:58
  • 2
    \$\begingroup\$ 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 \$\endgroup\$ – skibrianski Apr 16 '14 at 23:37
16
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ 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… \$\endgroup\$ – Wally Feb 15 '14 at 3:22
  • 1
    \$\begingroup\$ @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..? \$\endgroup\$ – daniero Feb 15 '14 at 4:06
  • \$\begingroup\$ @daniero Sounds reasonable - perhaps right at the edge of the spec. \$\endgroup\$ – Wally Feb 16 '14 at 0:59
3
\$\begingroup\$

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
\$\endgroup\$
  • 4
    \$\begingroup\$ 1 isn't really a prime. \$\endgroup\$ – elixenide Feb 15 '14 at 16:26
  • \$\begingroup\$ Uses a numerical array index - so at the edge of the spec. \$\endgroup\$ – Wally Feb 20 '14 at 14:56
  • \$\begingroup\$ Use pop instead of $ARGV[0], save 4 chars, remove numerical array index \$\endgroup\$ – mob Apr 16 '14 at 21:49
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I like the string decrement function - clear and concise. \$\endgroup\$ – Wally Feb 20 '14 at 14:36
1
\$\begingroup\$

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());
}
\$\endgroup\$
  • 1
    \$\begingroup\$ I'm not sure I see how this works, but I do see a numeric variable (i) and an arithmetic operator (i++). \$\endgroup\$ – Wally Feb 16 '14 at 1:05
  • \$\begingroup\$ Oh, didn't realise that I couldn't do a for loop like that.. will rewrite it tonight. \$\endgroup\$ – Sugendran Feb 19 '14 at 8:20
  • \$\begingroup\$ 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. \$\endgroup\$ – Sugendran Feb 19 '14 at 8:23
  • \$\begingroup\$ I've updated the code, it actually reduces the number of chars slightly :) \$\endgroup\$ – Sugendran Feb 19 '14 at 21:55
  • \$\begingroup\$ Cool. It looks like the same idea as the regex, but more efficient and explicitly showing the actual logic. \$\endgroup\$ – Wally Feb 20 '14 at 14:26
0
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ As above, 1 is not prime. \$\endgroup\$ – Wally Feb 20 '14 at 14:34
0
\$\begingroup\$

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

\$\endgroup\$

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