# Is it a prime? w/o math [closed]

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. • 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. – elixenide 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")) 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.

• 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)
});
}
// 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());
}

• 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

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