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 <= 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

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 2

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 3

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 4

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 5

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 6

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 7

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 8

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 9

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)