Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

This question already has an answer here:

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.

share|improve this question

marked as duplicate by Mhmd, ProgramFOX, Timtech, plannapus, user80551 Apr 9 at 11:48

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

3  
Probably because this is impossible? (Without abusing built-in prime functions, that is.) –  Doorknob 冰 Apr 7 at 20:48
2  
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 at 20:51
1  
@ProgrammerDan I added a solution using a typical prime-detection method. –  Ypnypn Apr 7 at 21:35
2  
Quite similar to Is it a prime? w/o math? –  daniero Apr 8 at 0:19
1  
In light of algorithmshark's solution; Should point two be updated to prohibit built in primality tests? –  Taemyr Apr 8 at 8:26

7 Answers 7

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 
share|improve this answer
5  
I believe this is the epitome of "two problems." +1 –  WChargin Apr 8 at 4:13

Sage, 18

Looks like this is allowed.

input()in Primes()

3 gives True, 4 gives False

share|improve this answer

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/

share|improve this answer
    
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 at 0:48
    
Thanks, any character will do, i used 'a'.. but I need the \1 for the capture. :-S –  ilmale Apr 8 at 0:52
    
A named capture helps: ('a'x($_=pop))=~/^a?$|^(?<a>aa+?)\g{a}+$/||print (48 bytes) –  Heiko Oberdiek Apr 8 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 at 1:03
1  
@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 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
share|improve this answer
6  
I feel that using a built in primality tester goes against the spirit of the challenge. –  Taemyr Apr 8 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 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.

share|improve this answer

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.

share|improve this answer
    
He shouldn't have to say it: meta.codegolf.stackexchange.com/a/1078/1416 –  corsiKa Apr 8 at 19:40

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!

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.