# 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? Feb 14, 2014 at 23:05
• If it has bonus points, it isn't code-golf Feb 14, 2014 at 23:12
• Added "natural" to specify bounds on the input. Feb 14, 2014 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. Feb 15, 2014 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 :) Feb 15, 2014 at 4:14

# 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… Feb 15, 2014 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..? Feb 15, 2014 at 4:06 • @daniero Sounds reasonable - perhaps right at the edge of the spec. Feb 16, 2014 at 0:59 ## 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. Feb 15, 2014 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. Feb 15, 2014 at 13:12 • Ok - I just couldn't find that construction well described anywhere! Feb 16, 2014 at 1:00 • I choose this as "the winner" since it goes out of the way to avoid even a hint of mathematics. Feb 20, 2014 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 Apr 16, 2014 at 23:37 ## 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. Feb 15, 2014 at 16:26 • Uses a numerical array index - so at the edge of the spec. Feb 20, 2014 at 14:56 • Use pop instead of $ARGV[0], save 4 chars, remove numerical array index
– mob
Apr 16, 2014 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. Feb 20, 2014 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++). Feb 16, 2014 at 1:05
• Oh, didn't realise that I couldn't do a for loop like that.. will rewrite it tonight. Feb 19, 2014 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. Feb 19, 2014 at 8:23
• I've updated the code, it actually reduces the number of chars slightly :) Feb 19, 2014 at 21:55
• Cool. It looks like the same idea as the regex, but more efficient and explicitly showing the actual logic. Feb 20, 2014 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. Feb 20, 2014 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