Determine if a number is prime without using arithmetic

Question

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.

Answer 1

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 

Answer 2

Sage, 18

Looks like this is allowed.

input()in Primes()

3 gives True, 4 gives False

Answer 3

PERL 53 54 52 48

('a'x($_=pop))=~/^a?$|^(?<a>aa+?)\g{a}+$/||print

Thanks to reddit: http://www.reddit.com/r/programming/comments/crmhe/regular_expression_to_check_for_prime_numbers_1111/

Answer 4

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

Answer 5

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.

Answer 6

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.

Answer 7

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!