Determine if a number is prime without using arithmetic [duplicate]

Write a program which determines if a given number is prime.

The catch: No digits or arithmetical operators. This means:

1. No digits from 0 to 9, anywhere in the program, and whatever the meaning
2. No using any built-in operators for addition (and incrementing), subtraction (and decrementing), multiplication, division, exponentiation, or modulus, anywhere in the program
3. This includes symbols like + and functions like num.add()
4. All other operations are permitted
5. You may define your own functions for the forbidden operations
6. You may use symbols like - when they mean things other than the forbidden operations

Shortest code wins - any language permitted.

Example solution

An ungolfed solution in Java can be found here.

marked as duplicate by Mhmd, ProgramFOX, Timtech, plannapus, user80551Apr 9 '14 at 11:48

• Probably because this is impossible? (Without abusing built-in prime functions, that is.) – Doorknob Apr 7 '14 at 20:48
• Even if not impossible, it is so exclusive of the established techniques for prime detection to be kind of silly ... Feel free to post to Sandbox first to get a feel for how things will turn out before you post. – ProgrammerDan Apr 7 '14 at 20:51
• @ProgrammerDan I added a solution using a typical prime-detection method. – Ypnypn Apr 7 '14 at 21:35
• Quite similar to Is it a prime? w/o math? – daniero Apr 8 '14 at 0:19
• In light of algorithmshark's solution; Should point two be updated to prohibit built in primality tests? – Taemyr Apr 8 '14 at 8:26

PHP, 117 characters

This one is based on regular expressions. If a string containing $n characters can be split into chunks of equal length, then$n must be composite.

(Assumes $n is a positive integer.) function p($n){$u=true;$s=str_repeat('x',$n);return($s!='x'&&!preg_match('/^(xx{'.$u.',})\\'.$u.'{'.$u.',}$/U',$s));}  Output: for ($i=1; $i<=100;$i++) if (p($i)) echo "$i ";

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

• I believe this is the epitome of "two problems." +1 – wchargin Apr 8 '14 at 4:13

Sage, 18

Looks like this is allowed.

input()in Primes()


3 gives True, 4 gives False

PERL 535452 48

('a'x($_=pop))=~/^a?$|^(?<a>aa+?)\g{a}+$/||print  • Interesting. However, from the question: "1. No digits from 0 to 9, anywhere in the program, and whatever the meaning." The variable can be read in a shorter way: $a=pop; – Heiko Oberdiek Apr 8 '14 at 0:48
• Thanks, any character will do, i used 'a'.. but I need the \1 for the capture. :-S – ilmale Apr 8 '14 at 0:52
• A named capture helps: ('a'x($_=pop))=~/^a?$|^(?<a>aa+?)\g{a}+$/||print (48 bytes) – Heiko Oberdiek Apr 8 '14 at 0:57 • Thanks you, I was looking for a short way to use name reference. Also I didn't know the empty print trick. :D – ilmale Apr 8 '14 at 1:03 • @SeanCheshire Rule 3 only seems to disallow using + as an arithmetic operator, not as a regex symbol. This is in contrast to rule 1, which expressly forbids any use of digits in any context. – Venge Apr 8 '14 at 22:44 J - 7 char Trivial. (p:~=~)  This verb is in the form of a hook. Applied to an argument y, it will evaluate as follows. (Feel free to check for yourself: Hook, Reflex/Passive, Equals, Primes.) (p:~=~) y NB. (F G) y becomes y F (G y) (Hook) y p:~ (=~ y) NB. x F~ y becomes y F x (Passive) (=~ y) p: y NB. F~ y becomes y F y (Reflex) (y = y) p: y NB. anything is equal to itself, so y=y becomes 1 1 p: y NB. 1 p: y tests for primality of y  Usage:  (p:~=~) 5 1 (p:~=~) 6 0 (p:~=~) 8675309 1 NB. test every element of a list (p:~=~)every 1627 5231 7610 6311 4549 6990 4220 9028 4066 3496 1 1 0 1 1 0 0 0 0 0  • I feel that using a built in primality tester goes against the spirit of the challenge. – Taemyr Apr 8 '14 at 8:27 • @Taemyr (*@{.=*./)@(+.}.@i.) for 20 char. +. is GCD, *. is LCM, * is Signum. But until the specs change, the 7 char solution is the shortest valid solution. – algorithmshark Apr 8 '14 at 19:36 Python 3, 85 (lambda i:not any(' '*i==(' '*u)*v for u in range(i)for v in range(i)))(int(input()))  Where * is not a multiplication operator but a string multiple self-concatenation operator. Ruby, 30 require'prime';f=->n{n.prime?}  Declares a function that returns whether its argument is prime. Alternative version (same length): require'prime';f=proc &:prime?  Obviously bending the rules, but you never said built-in prime functions aren't allowed. PHP - 208 <?php function i($n){if($n==strlen(" "))return!!"";foreach(range(strlen(" "),$n) as$_){if($_!=$n){$a=array_fill(!!"",$n,"");while(count($a)>=$_)array_splice($a,!!"",$_);if(!count($a))return!!"";}}return!"";}


Type juggling in PHP is fun!