# Is it a prime? w/o math

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

## 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.

-
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 '14 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 '14 at 13:12
Ok - I just couldn't find that construction well described anywhere! –  Wally Feb 16 '14 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 '14 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 Apr 16 '14 at 23:37

# 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.

-
+1 because your score is 42. –  Justin Feb 14 '14 at 23:06
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 '14 at 3:22
@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 '14 at 4:06
@daniero Sounds reasonable - perhaps right at the edge of the spec. –  Wally Feb 16 '14 at 0:59

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

## 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"))
``````

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.

-
I like the string decrement function - clear and concise. –  Wally Feb 20 '14 at 14:36

# 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)
});
}
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());
}
``````
-
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 '14 at 1:05
Oh, didn't realise that I couldn't do a for loop like that.. will rewrite it tonight. –  Sugendran Feb 19 '14 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 '14 at 8:23
I've updated the code, it actually reduces the number of chars slightly :) –  Sugendran Feb 19 '14 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 '14 at 14:26

## 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
``````
-
As above, 1 is not prime. –  Wally Feb 20 '14 at 14:34

# 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
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
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
``````
-
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 '14 at 14:39

## 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

-