Self-shortening Prime Tester

Question

Let's get right in to it. Your challenge is to make a program that does these things depending on its input:

1. If the input is a number, output "Prime" if the number is a prime number and "Not prime" if the number isn't a prime number. You can assume the number is > 1.

2. If the input is two numbers, output every single prime number between the first number (inclusive) and the second number (exclusive). You can assume the first number is smaller than the second.

3. Here comes the real challenge: if there's no input, the program should output a shorter version of itself that does exactly the same things as the original program. The program is not allowed to read from any file or from the web. The new program should also be able to do this. It should work for at least 5 generations. The new program doesn't have to be in the same language as the first.

Scoring:

Your score is equal to the sum of the number of bytes in the first five generations of your submission (the submission itself being generation one). If the new code is hard-coded in to the first program, multiply the score by 1.5. Lowest score wins. (If you find some kind of flaw in the scoring system, please let me know in the comments)

Answer 1

CJam, 66 + 65 + 64 + 63 + 62 = 320 325 355 bytes

The following 5 lines are the first 5 generations:

{     `(\1>+q~](\_,["_~"a{~mp'P"Not p"?"rime"@;}{~,>{mp},p;}]=~}_~
{    `(\1>+q~](\_,["_~"a{~mp'P"Not p"?"rime"@;}{~,>{mp},p;}]=~}_~
{   `(\1>+q~](\_,["_~"a{~mp'P"Not p"?"rime"@;}{~,>{mp},p;}]=~}_~
{  `(\1>+q~](\_,["_~"a{~mp'P"Not p"?"rime"@;}{~,>{mp},p;}]=~}_~
{ `(\1>+q~](\_,["_~"a{~mp'P"Not p"?"rime"@;}{~,>{mp},p;}]=~}_~

The last one produces

{`(\1>+q~](\_,["_~"a{~mp'P"Not p"?"rime"@;}{~,>{mp},p;}]=~}_~

which still performs the prime tasks correctly.

Test it here.

Explanation

The basic CJam quine is

{"_~"}_~

which can be extended very easily to a generalised quine. For an explanation of this see my answer here.

The basic ideas for this answer are:

• Start the quine with a bunch of spaces and remove one of these when quining.
• Get an array with all input numbers (0, 1 or 2) and choose some code to run depending on the length (by using it to index into an array).

Here is a breakdown of the code inside the quine:

"Remove a space from the block's string representation:";
`(\1>+
`      "Get the string representation of the block.";
 (\    "Slice off the leading '{' and pull the remaining string back up.";
   1>  "Remove the first character, i.e. a space.";
     + "Prepend the '{' to the string again.";

"Get the array of inputs and choose the code:";
q~](\_,[...]=~
q~             "Read and eval the input.";
  ]            "Wrap everything (including the string for the block) in an array.";
   (\          "Shift off the string and swap it with the rest of the array.";
     _,        "Duplicate the input array and get its length.";
       [...]=  "Use it to index into this array.";
             ~ "If there are no inputs there will now be an array on the top of the
                stack, which ~ will unwrap. Otherwise there will be a block which ~
                will evaluate.";

"If there is no input, push the string needed for the quine and put it in
 an array for ~ to unwrap:";
"_~"a

"If there is one input, test for primality:";
~mp'P"Not p"?"rime"@;
~mp                   "Unwrap the input array and test for primality.";
   'P"Not p"?         "Choose either 'P' or 'Not p' depending on the result.";
             "rime"   "Push the common part of the string.";
                   @; "Pull up the quine string and discard it.";

"If there are two inputs, print an array with all the primes in the range:";
~,>{mp},p;
~          "Unwrap the array leaving N and M on the stack.";
 ,         "Get a range [0 1 .. N-1].";
  >        "Drop the first M elements, giving [M M+1 .. N-1].";
   {mp},   "Filter to keep only the primes.";
        p  "Pretty-print the array.";
         ; "Discard the quine string.";

Answer 2

C, Score: 553 + 552 + 551 + 550 + 549 = 2755,

Original Length: 553, Avg: 551

EDIT: Only 5 generations, not 6!

Looks like Martin beat me both in time and in score (by nearly an order of magnitude!). Ah, well.

The original program is as follows:

char*c="char*c=%c%s%c;k=%d,a;p(c,v,d){for(v=2;v<c;v++)d+=!(c%cv);return!d;}int main(int C,char**V){if(C==1){printf(c,34,c,34,k/10,37,34,34,34,34,34,37,34);return 0;}a=atoi(V[1]);if(C==2)printf(p(a,0,0)?%cPrime%c:%cNot prime%c);if(C==3)for(;a<atoi(V[2]);a++)if(p(a,0,0))printf(%c%cd %c,a);}";k=10000,a;p(c,v,d){for(v=2;v<c;v++)d+=!(c%v);return!d;}int main(int C,char**V){if(C==1){printf(c,34,c,34,k/10,37,34,34,34,34,34,37,34);return 0;}a=atoi(V[1]);if(C==2)printf(p(a,0,0)?"Prime":"Not prime");if(C==3)for(;a<atoi(V[2]);a++)if(p(a,0,0))printf("%d ",a);}

I'll unravel it a little bit for better understanding, but for it to work properly the new lines are NOT part of the program.

char*c="char*c=%c%s%c;k=%d,a;p(c,v,d){for(v=2;v<c;v++)d+=!(c%cv);return!d;}int main(int C,char**V){if(C==1){printf(c,34,c,34,k/10,37,34,34,34,34,34,37,34);return 0;}a=atoi(V[1]);if(C==2)printf(p(a,0,0)?%cPrime%c:%cNot prime%c);if(C==3)for(;a<atoi(V[2]);a++)if(p(a,0,0))printf(%c%cd %c,a);}";
k=10000,a;
p(c,v,d){
    for(v=2;v<c;v++)
        d+=!(c%v);
    return!d;
}
int main(int C,char**V){
    if(C==1){
        printf(c,34,c,34,k/10,37,34,34,34,34,34,37,34);
        return 0;
    }
    a=atoi(V[1]);
    if(C==2)
        printf(p(a,0,0)?"Prime":"Not prime");
    if(C==3)
        for(;a<atoi(V[2]);a++)
            if(p(a,0,0))
                printf("%d ",a);
}

The only thing that changes from program to program is the value of k, which loses exactly one digit every iteration. Interestingly, after the 5th generation, k becomes zero and stays there, so you can iterate ad infinitum and always have valid output.

Answer 3

Tcl 253 + 252 + 251 + 250 + 249 = 1255 bytes

eval [set x {     proc q a\ b {incr b;expr $a%$b?\[q $a $b]:$a==$b}
proc 1 a {if [q $a 1] puts\ Prime {puts Not\ Prime}}
proc 2 a\ b {while $b-\$a {if [q $a 1] puts\ $a;incr a}}
proc 0 {} {puts "eval \[set x {[string ra $::x 1 end]}]"}
$argc {*}$argv}]

The code needs to end with a newline. Explanation:

eval [set x {...}]

Write the code into x, then execute it.

$argc {*}$argv

Execute the command which name is the argument length, passing the arguments along.

proc q a\ b {incr b;expr $a%$b?\[q $a $b]:$a==$b}

Returns 1 when a is prime, 0 else. Uses recursion; the second backslash prevents command substitution from the interpreter and enables the one from expr (which is lazy).

proc 1 a {if [q $a 1] puts\ Prime {puts Not\ Prime}}
proc 2 a\ b {while $b-\$a {if [q $a 1] puts\ $a;incr a}}

Straightforward implementation of the requirements.

proc 0 {} {puts "eval \[set x {[string ra $::x 1 end]}]"}

This is the quine, stripping a space from the beginning each time.