12
\$\begingroup\$

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.

\$\endgroup\$

marked as duplicate by Mhmd, ProgramFOX, Timtech, plannapus, user80551 Apr 9 '14 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.

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

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 
\$\endgroup\$
  • 5
    \$\begingroup\$ I believe this is the epitome of "two problems." +1 \$\endgroup\$ – wchargin Apr 8 '14 at 4:13
15
\$\begingroup\$

Sage, 18

Looks like this is allowed.

input()in Primes()

3 gives True, 4 gives False

\$\endgroup\$
10
\$\begingroup\$

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/

\$\endgroup\$
  • \$\begingroup\$ 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; \$\endgroup\$ – Heiko Oberdiek Apr 8 '14 at 0:48
  • \$\begingroup\$ Thanks, any character will do, i used 'a'.. but I need the \1 for the capture. :-S \$\endgroup\$ – ilmale Apr 8 '14 at 0:52
  • \$\begingroup\$ A named capture helps: ('a'x($_=pop))=~/^a?$|^(?<a>aa+?)\g{a}+$/||print (48 bytes) \$\endgroup\$ – Heiko Oberdiek Apr 8 '14 at 0:57
  • \$\begingroup\$ Thanks you, I was looking for a short way to use name reference. Also I didn't know the empty print trick. :D \$\endgroup\$ – ilmale Apr 8 '14 at 1:03
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Venge Apr 8 '14 at 22:44
7
\$\begingroup\$

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
\$\endgroup\$
  • 6
    \$\begingroup\$ I feel that using a built in primality tester goes against the spirit of the challenge. \$\endgroup\$ – Taemyr Apr 8 '14 at 8:27
  • \$\begingroup\$ @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. \$\endgroup\$ – algorithmshark Apr 8 '14 at 19:36
5
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$

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