Finding prime numbers without using "prime characters"

Question

Your task, if you choose to accept it, is to write a program/function that accepts an integer \$N\$ as input. The program/function should output/return a list of the first \$N\$ prime numbers. But here's the catch: you are not allowed to use prime characters in your code. A prime character is a character whose Unicode code point is a prime number. In the printable ASCII range, these are:

%)+/5;=CGIOSYaegkmq

But the rule also applies to non-ASCII characters if your code uses those.

• A valid input is an integer \$N\$ where \$0 < N \le T\$, where you can choose \$T\$, but it has to be greater than or equal to \$10000\$. \$T\$ does not have to be finite.
• For invalid inputs (non-integers, integers out of range), throw an exception or output/return nothing/null.
• An integer with leading/trailing whitespace as input is considered invalid.
• An integer with a + as sign character as input is considered invalid.
• An integer with leading zeros as input is considered valid.
• If your language allows you to pass an already-parsed integer as input, the above parsing rules (except the range one) don't apply, because the int is already parsed.
• The input is always base-10.
• Use of built-in prime generators and primality testers (this includes prime factorization functions) is not allowed.
• The source restriction is imposed on Unicode characters, but the byte counting for the score can be in another encoding if you wish.
• The output can contain a single trailing newline, but this is not required.
• If you output/return the prime number list as a string, then every prime number must be delimited by one or multiple non-digit char(s). You can choose which delimiter you use.
• This is a code-golf challenge, the shortest code in bytes wins.

Stack Snippet to verify your code

You can use the below Stack Snippet to verify that your code does not contain prime chars:

var primes=[],max=10000;for(var i=2;i<=max;i++){primes.push(i);}for(var N=2;N<Math.sqrt(max);N++){if(primes.indexOf(N)===-1){continue;}primes=primes.filter(function (x){return x===N||x%N!==0;});}function setText(elem,text){var z=('innerText' in elem)? 'innerText' : 'textContent';elem[z]=text;}function verify(inputCode,resultSpan){var invalidChars=[];var success=true;for(var i=0;i<inputCode.length;i++){var cc = inputCode.charCodeAt(i);if (cc>max){setText(resultSpan,"Uh oh! The char code was bigger than the max. prime number calculated by the snippet.");success = false;break;}if (primes.indexOf(cc)!==-1){invalidChars.push(inputCode[i]);}}if (invalidChars.length===0&&success){setText(resultSpan, "Valid code!");}else if(success) {  var uniqueInvalidChars = invalidChars.filter(function (x, i, self){return self.indexOf(x)===i;});setText(resultSpan, "Invalid code! Invalid chars: " + uniqueInvalidChars.join(""));    }}document.getElementById("verifyBtn").onclick=function(e){e=e||window.event;e.preventDefault();var code=document.getElementById("codeTxt").value;verify(code,document.getElementById("result"));};

Enter your code snippet here:<br /><textarea id="codeTxt" rows="5" cols="70"></textarea><br /><button id="verifyBtn">Verify</button><br /><span id="result"></span>

Answer 1

Python 3.7+, 183 bytes

for E,E.__clªss_ᵍᵉtitᵉᵐ__ in[__builtins__.__loªdᵉr__,ᵉxᵉc],:E[f'd{101:c}f F(n\x29:\n p,f\x3d1,1\n whil{101:c} n>0:p,f\x3d-~p,f*p*p\73n-\x3df{37:c}p>0!\x3dprint(p\x29']

Try it online!

Assumes an infinite upper bound, takes integer input via function argument, and prints the primes on separate lines.

Without substitutions for characters (except \n):

for E,E.__class_getitem__ in[__builtins__.__loader__,exec],:E[f'def F(n):\n p,f=1,1\n while n>0:p,f=-~p,f*p*p;n-=f%p>0!=print(p)']

The string in the above code:

def F(n):
 p,f=1,1
 while n>0:p,f=-~p,f*p*p;n-=f%p>0!=print(p)

Python 3.7 added the __class_getitem__ magic method: if A is a class, then A[x] calls A.__class_getitem__(x). Assigning exec to this attribute of a class allows us to call it without ). Unfortunately, we cannot create our own class without either using the class keyword (a) or calling the type function ()), so we must use a built-in class. The only one that allows the assignment to be made without error is __builtins__.__loader__.

Python normalizes all identifiers to NFKC, and this allows us to spell __class_getitem__, __loader__, and exec without using any of the letters aegm. The exact substitutions are U+00AA for a, U+1D49 for e, U+1D4D for g, and U+1D50 for m. We use a for loop to make assignments without using =, and these let us call exec via E[f'...'] in the body.

Inside the string passed to exec, we use octal (\73 instead of ;), hex (\x3d instead of =), and decimal ({37:c} instead of %) escapes for banned characters. The code simply tests the primality of each positive integer using Wilson's theorem. A function was used instead of a lambda as the recursion limit causes the latter to stop working well below 10000.

Answer 2

CJam, 19 18 30 34 33 19 17 21 20 bytes

Try it online.

{_3\#,2>__ff*:~-<N*}

This is probably one of the most horribly inefficient algorithms I've ever implemented. But I did it for the size!

My answer consists of a code block, which acts like an anonymous function in CJam. Run it with an integer immediately preceding it on the stack, and the resulting list is dumped onto the stack. I treat the upper bound on the input as infinite so I don't have to check that bound.

My algorithm starts by raising 3 to the inputth power, which is guaranteed to give a number larger than the input-th prime if the input is valid. Then a list of the integers from 2 to this number minus one is generated, which is a large enough swath to contain all the prime numbers we want. To get rid of the composite numbers... sigh... we create a list of every pairwise product, which should generate all composite numbers from 4 to some stupidly large value, large enough for our purposes. Then it's just a matter of removing every element from the original list that is in this composite list, trimming it down to the first input elements, and joining the elements with the newline character.

The algorithm should work for any input. However, whether or not the interpreter/computer has enough memory or time is a whole other question, because the time and space requirements are exponential with respect to the input. So if the input is larger than about 5 for the online interpreter or about 8 for the offline one, then the answer to that question is probably no.

Answer 3

Java. 474 bytes

i\u006dport j\u0061v\u0061.util.*\u003bvoid b(int b\u0029{Lon\u0067 c\u003d2L,d,f[]\u003d{}\u003bfor(f\u003dArr\u0061ys.copy\u004ff(f,b\u0029,Arr\u0061ys.fill(f,0L\u0029\u003bb-->0\u003b\u0029for(d\u003d0L\u003bf[b]<1\u003bf[b]\u003dd<1?c:f[b],d\u003d0L,c\u002b\u002b\u0029for(lon\u0067 h:f\u0029d\u003dh>0&&c\u002fh*h\u003d\u003dc?1:d\u003bj\u0061v\u0061x.x\u006dl.bind.JAXB.un\u006d\u0061rsh\u0061l(""\u002bArr\u0061ys.\u0061sList(f\u0029,Lon\u0067.cl\u0061ss\u0029\u003b}

Takes input via function argument, outputs via thrown exception.

Indented:

i\u006dport j\u0061v\u0061.util.*\u003b
void b(int b\u0029{
    Lon\u0067 c\u003d2L,d,f[]\u003d{}\u003b
    for(f\u003dArr\u0061ys.copy\u004ff(f,b\u0029,Arr\u0061ys.fill(f,0L\u0029\u003bb-->0\u003b\u0029
        for(d\u003d0L\u003bf[b]<1\u003bf[b]\u003dd<1?c:f[b],d\u003d0L,c\u002b\u002b\u0029
            for(lon\u0067 h:f\u0029
                d\u003dh>0&&c\u002fh*h\u003d\u003dc?1:d\u003b
    j\u0061v\u0061x.x\u006dl.bind.JAXB.un\u006d\u0061rsh\u0061l(""\u002bArr\u0061ys.\u0061sList(f\u0029,Lon\u0067.cl\u0061ss\u0029\u003b
}

Escaped characters removed:

import java.util.*;
void b(int b){
    Long c=2L,d,f[]={};
    for(f=Arrays.copyOf(f,b),Arrays.fill(f,0L);b-->0;)
        for(d=0L;f[b]<1;f[b]=d<1?c:0,d=0L,c++)
            for(long h:f)
                d=h>0&&c/h*h==c?1:d;
    javax.xml.bind.JAXB.unmarshal(""+Arrays.asList(f),Long.class);
}

Explanation:

Long c,d,f[]={};                                                //Initialize variables.

for(f=java.util.Arrays.copyOf(f,b),Arrays.fill(f,0L);b-->0;)
    f=java.util.Arrays.copyOf(f,b),Arrays.fill(f,0L)            //Initialize f to an array of 0's.
                                                     b-->0      //Iterate over the first b primes.

for(d=0L;f[b]<1;f[b]=d<1?c:0,d=0L,c++)
    d=0L                        d=0L                            //Initialize d to 0.
         f[b]<1                      c++                        //Increment c while the b'th prime is 0.
                f[b]=d<1?c:0                                    //If d = 0, the b'th prime = c, else continue.

for(long h:f)                                                   //Iterate over all found primes.

d=h>0&&c/h*h==c?1:d;
  h>0                                                           //Ignore non-found primes.
       c/h*h==c                                                 //Equivalent to c%h==0
               ?1:d                                             //If h is prime and c is divisible by h, d = 1. Otherwise d stays unchanged.

javax.xml.bind.JAXB.unmarshal(""+Arrays.asList(f),Long.class)   //Print solution to stderr
javax.xml.bind.JAXB.unmarshal(                   ,Long.class)   //Prints what's contained to stderr.
                                 Arrays.asList(f)               //Convert f to list.
                              ""+                               //Convert to string.

My original solution used a return statement. After asking this question on StackOverflow, regettman was kind enough to provide a way to output/return without using prime letters.

As usual, suggestions are welcome :)

Answer 4

Ruby, 74

->n,*o{o<<[2..n*n][0].find{|x|!o.find{|y|1.>x.^y.*x.div y}}until o[n-1]
o}

Explanation:

*o initializes an empty output array. until it has n items, we find the smallest number >=2 that doesn't divide any item currently in o, then add it to o. To test for division, yikes. All the good operators are disallowed, and I can't even use divmod. Best I could see was to use x.div y, which takes x divided by y and rounds down, then multiply that by y again. If it equals x, there was no rounding, so y divides x. 1.>x.^ is an equality test, checking whether the result of xor is 0. The . before every operator is because you can't mix .-free operator calls and parenthesis-free method calls.

Edit: The range-checking specifications were added after I posted this, I think. To comply requires 79 characters:

->n,*o{o<<[*2..-~n*n].find{|x|!o.find{|y|1.>x.^y.*x.div y}}until o[n-1]||n<1
o}

Answer 5

CJam, 38 37 30 bytes

{_~2#,2>\{(\{1$37c~},\p}*'<(~}

Try it here

I think this should comply with all the rules and works for any non-negative N (i.e. T is infinite). It's horribly inefficient though, so don't try it for large numbers.

This is a block - the closest thing to an (unnamed) function - which expects an integer on the stack, prints all the prime numbers and leaves the stack without its input. For all invalid inputs it will either throw an error or print nothing.

Most of the code is input validation, followed by the sieve of Eratosthenes. I only needed to work around the input restriction in 3 places:

• ) is increment in CJam. I needed that once, but could replace it with ~ (bitwise complement) because I was squaring the numbers afterwards anyway.
• % is modulo. I'm using 37c~ instead, which first creates the character % and then eval's that. This makes the code a lot slower.
• ; pops and discards an element from the stack. I need to do this at the end. Instead I'm using '<(~ which pushes the character <, decrements it and eval's that.

Answer 6

Bash + coreutils, 227 bytes

printf -vb br`dc<<<Di14B8209P`
printf -vc -- $[$1-0]
[ "${1#$c}" -o $c -lt 1 ]||{
for i in {2..104729}
{
for f in `jot $[i-1] $[i-1] 1`
{
[ 0 -lt `dc<<<"$i $f~p"` ]||$b
}
[ $f -lt 2 ]&&printf $i\ &&: $[c--]
[ $c -lt 1 ]&&$b
}
}

This was quite tricky. Some things I ran into:

• Most loops (while and until) are unusable because they most close with done which is a shell keyword and cannot be the result of a variable expansion (unless eval is used, but that is out too). The only usable loop is for/in which allows {/} instead of do/done. for (( ; ; )) is also not usable.
• = is out, so we need another way to assign variables. printf -v is good for this.
• We know that p(10000) is 104729 so for the outer loop for potential primes we can simply loop from 2 to 104729 and break once we have enough primes
• jot generates the list of potential factors in the inner loop. If a potential factor divides a potential prime, then it is not prime and we break out early
• Fortunately break is a shell builtin and not a keyword, so may be generated as a result of an expansion. dc converts a base 13 number to the bytestream eak.
• To check if a potential factor divides a potential prime, we cannot use the usual / or % shell arithmetic operators. So this is outsourced to dcs ~ operator, which pushes quotient and remainder to the stack.
• -lt - less-than - is the only usable shell comparison operator.
• echo is no use for output. printf works though as long as we avoid %

Getting the input validation right is a bit of a pain. This returns nothing in the case of invalid input.

Output:

$ ./primenoprime.sh 10
2 3 5 7 11 13 17 19 23 29 $ 

Answer 7

Rust, 2720 1695 bytes

|n|for i in 0..n{if i<3&&i>1||i&1>0&&0<[0x2196820D864A4c32816D129A64B4cB6Eu128,0x4A2882D129861144A48961204A0434c9|1<<28,0x148A48844224064B0834992132424030|1<<80,0x64048928124108A00B40B4086c304204|1<<0|1<<84|1<<120,0xc02104c94112422180124496804c3098,0x220824B0826896810804490000982D32|1<<104,0x69009244304340069004264940A28948|1<<36,0x86122D22400c06012410DA408088210,0x14916022c044A0020110D301821B0484,0x4cA2100800422094092094D204A6400c|1<<84,0x34c108144309A24A48B081041018200|1<<28|1<<64,0x241140A2180032402084490880422402|1<<8|1<<20|1<<68,0x29260008360044120A41A00101840128|1<<72,0xc20c26484822006D10100480c0618283|1<<100,0x10c02402190024884420482024894810|1<<44|1<<7*8|1<<104,0x60901300264B0400802832cA01140868,0x430800112186430c32100100D0248082|1<<16,0x24880906002D20430092900c10480424,0x4000814196800880430082090932c040|1<<60,0x926094022080c3292048489608481048|1<<4*13,0xA04204901904004A0104422812000|1<<7*8,0x800084424002982c02c801348348924|1<<96,0x1864328244908A0004D0048442043698|1<<28|1<<112,0x861104309204A44028024001020A0090,0x4424990912486084c90804422c004208|1<<36,0x4040208804321A011000211403002400|1<<88,0xA2020c90116802186030014084c30906,0x8801904800841028224148929860004,0x120100100c061061020004A442681210,0x140128040A0c94186412422194032010|1<<7*8,0x4882402D20410490014000D040A40A29,0x822902002484490424080130100020c1|1<<76,0xA0cA0006112100104816814802486100|1<<20,0x2414480906810c044200B09104000240|1<<120,0x84420004802c10c860A00A011242092|1<<16|1<<112,0x12824414814804820022130406980032,0x2c00D86424812004D028804340101824,0x180110c04120cA41020000A241081209,0x48044320240A08320941220A41804A4,0x820104128864008A6086400c001800|1<<96][i>>8]&1<<{[i&{1<<8}-1][0]>>1}{print!{"{}
",i}}}

Try it online!

Lookup table generator

Yikes, I'm fairly confident rust doesn't even count as primitive recursive with the restrictions, because mutability and function calls are disallowed, meaning there is no way to maintain state across loop iterations. Works up to 10111.

My strategy was to form a lookup table by packing the primality of every odd number into array of 128 bit integers, and then just using a good old fashioned mask and shift to recover the value. The 5s in the hexadecimal representation are dealt with by removing the 1 bit and orring it in at runtime. To deal with operator precedence issues, I abused the fact that blocks are also expressions, so I can use curly braces instead of parentheses.

Answer 8

Haskell, 90 bytes

\n->[fst c|c<-zip[p|p<-[2..],not$or[b>p-1&&b-1<p|b<-[u*v|u<-[2..p-1],v<-[2..p-1]]]][1..n]]

This is an anonymous function which takes an integer n as input.

How it works: [p|p<-[2..],not$or[b>p-1&&b-1<p|b<-[u*v|u<-[2..p-1],v<-[2..p-1]]]] (first example of prime number one-liners at the Haskell wiki but with the elem function replaced) creates an infinite list of primes. zip it with the numbers from 1to n to make a list of (prime, seq. number) pairs. Remove seq. number, again. Result is a list of primes of length n.

Answer 9

Rust, 64897 bytes

|n|println!{"{:?}",&[2,3,6-1,7,11,13,17,19,23,29,31,37,41,43,47,60-7,0x3b,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,0x97,0x9d,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,0xfb,0x101 ...}

(code snipped due to character limit, full solution here)

The following rust features become unavailable due to the prime restriction:

• function calls, as they require ')'
• regular bindings, since they require let (e)
• macro definitions, they require macro-rules! (a,e,m)
• match statements, they require match (a,m) and => (=)
• mutability, since it's always introduced with the mut keyword (m).
• return (e), break (a,e), continue (e)
• else (e)

What you can technically use:

• if. But without else, they're useless in expression contexts, so only good for side effects.
• macros. Standard macros like print! are usually followed by (), but it's actually legal to use {} or [] instead. Without this, the task would be impossible.
• closures, in the most narrow sense. You can't call them (requires ()) or bind them(requires let), but you can define a single non-recursive one. Without this, the task would obviously become impossible.
• structs.
• for loops. These are promising, since they actually allow variable binding, and they take an iterator, which can still be defined with the range syntax. The iterator can even be an expression.
• Builtin operators, except +, % and /. The short-circuiting logical operators seem promising.

I simply couldn't make anything Turing-complete with these tools. I'm sorry. All that was left was to include the full first 10000 primes, cleaned of 5's. At least you can slice it and have a valid solution, in the most narrow sense possible.

I very much would like experts on Turing tarpit diving (or on Rust!) to tell me if I could have done anything better!

Answer 10

GNU APL, 75 68 67 65 59 56 55 characters

⎕IO must be 1.

∇z←p n
z←2,j←3
j←j--2
→2×⍳∨⌿1>z|j
z←z,j
→2×⍳n>⍴z
z←n↑z∇

I came back on this months later realizing that I had an extra space!

Answer 11

Jelly, 9 bytes

2ḍƇ`L<3Ʋ#

Try it online!

The character codes are [50, 7693, 391, 96, 76, 60, 51, 434, 35]

How it works

2ḍƇ`L<3Ʋ# - Main link. Takes N on the left
       Ʋ  - Define a monad f(k):
  Ƈ       -   Filter the range [1, 2, ..., k] on the following:
 ḍ `      -     Divides k cleanly?
    L     -   Length
     <3   -   Less than 3?
2       # - Count up k = 2, 3, 4, ... until n integers return true. 
            Return those integers

Answer 12

JavaScript (V8), 131 bytes

[].fill.constructor`M${`for(N\x3D1\x3bM\x3bn-N||--M-print(n\x29\x29for(n\x3Di\x3DN-\x3D-1\x3bi-->2\x3b\x29n\x2fi-~~[n\x2fi]||n--`}`

Try it online!

Answer 13

Pyth - 12 bytes

Uses pyth's prime factorization function to see if # is prime. Uses !tPT trick suggested to me at my answer for primes under million problem.

<f!tPTr2^T6Q

Since the filter only works for primes under n and not first n, I just looked up the inverse of pi(x) for 10,000 and got 104,000 so I use primes under 10⁶ and get first n. This doesn't actually run, so you should test by replacing ^T6 with ^T3 and restrict n to under 1000. Input from stdin and output to stdout.

<          Q     Slice first n
f     r2^T6      filter on range 2->10⁶
 !               Logical not (gives true if tail is empty)
  t              Tail (all but first, so gives empty if prime fact is len 1)
   PT            Prime factorization of filter var (len 1 if num is prime)

Answer 14

05AB1E, 11 bytes

∞¦ʒDÑPQ}sôн

Input as integers.

Try it online or verify it's valid, and some test cases.

Or 14 bytes if we include string inputs, and comply to the other rules:

• Non-integer strings; leading whitespaces; or leading + are invalid
• Leading 0 are valid

∞ʒDÑPQ}s0ì>ôн¦

Try it online or verify it's valid, and some test cases.

Explanation:

∞        # Push an infinite positive list: [1,2,3,...]
 ¦       # Remove the leading 1: [2,3,4,...]
  ʒ      # Filter it by:
   D     #  Duplicate the current integer
    Ñ    #  Pop and push a list of its divisors
     P   #  Take the product of this list of divisors
      Q  #  Check if it's still the same as the duplicated integer
         #  (only if the divisors are {1,value}, the value will be a prime)
  }s     # After the filter: swap so the (implicit) input-integer is a the top
    ô    # Split the infinite list into parts of that size
     н   # Pop and leave just the first part

For the program with additional string input validation:

• The 0ì will prepend a leading "0" to the input (to fix the test cases with leading +, which would otherwise be interpret as integers);
• The > will then increase the string-integer by 1 (implicitly converting it to an integer if it's valid first), because we haven't removed the leading 1 with ¦ yet;
• The ¦ will then:
  • Remove the leading 1 from the list for valid inputs;
  • Or remove the 1 from itself, leaving an empty string for invalid inputs. Because the s0ì>ô will have been no-ops, after which н will leave not the first part, but the first integer in the list, which is the 1.

Minor notes:

1. Uses 05AB1E encoding, with the following codepoint-integers.
2. ôн could have been £, but unfortunately £ with code-point 163 is a prime.
3. Even if prime-builtins were allowed, Å in the builtin Åp with code-point 197 is a prime as well. Although <ÝØ would in that case be a short 'valid' alternative: Try it online or verify it's 'valid', and some test cases. <Ý pushes a list in the range [0,input), whereas Ø converts each value in this list to their 0-based value'th prime.