Self-shortening Prime Tester
CJam, 66 + 65 + 64 + 63 + 62 = 320 325 355  bytes

The following 5 lines are the first 5 generations:

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


The last one produces

{`(\1&gt;+q~](\_,["_~"a{~mp'P"Not p"?"rime"@;}{~,&gt;{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&gt;+
`      "Get the string representation of the block.";
 (\    "Slice off the leading '{' and pull the remaining string back up.";
   1&gt;  "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:";
~,&gt;{mp},p;
~          "Unwrap the array leaving N and M on the stack.";
 ,         "Get a range [0 1 .. N-1].";
  &gt;        "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.";