## A more efficient use of `Select`

If the likely bound of the problem is easily stored in memory it is practical to generate a `Range`, which is fast, and then `Select` from that.  Since the `Range` will be unpacked by `Select` you must consider the *unpacked* size.  For example:

    ByteCount @ Developer`FromPackedArray @ Range@1*^7

> 240 000 032

This is a reasonable starting size in many cases.  

Finding five values take a quarter of a second:

    Select[Range@1*^7, PrimeQ[#^6 + 1091] &, 5] // Length // Timing

>     {0.249, 5}

Fining all values with a seed <= 10^7:

    Select[Range@1*^7, PrimeQ[#^6 + 1091] &] // Length // Timing

>     {19.797, 3338}

You can see that this scales pretty well, without excessive overhead in the case that values are found quickly, yet for your search 3338 results can be found before the limit is reached.

(The seeds found with this method need to be converted to primes with `#^6 + 1091 &`.)

## A method for larger problems

If this will not work, either because you have no idea what the likely upper bound is, or it is too high to hold a `Range` in memory, then it will be most efficient to operate in blocks, due to *Mathematica*'s vector optimizations.

First, there is a more efficient way to build the list of candidates:

    Range[100]^6 + 1091

This takes full advantage of the vectorized operations available.  

Pick a large enough block size that the average element processing time is relatively low, but not so large as to process more elements than are likely needed.  I will pick a block size of 100,000 and I will try to find 5,000 solutions:

    block = 100000;
    
    result = {};
    
    find = 5000;
    
    hits = 0;
    
    Do[
      If[hits >= find, Return["Done!"]];
      Select[(n block + Range[block])^6 + 1091, PrimeQ] //
       (result = {result, #}; hits += Length@#) &,
      {n, 0, 1*^9}
    ] ~Monitor~ n

The results are stored in a linked list rather than using `Sow`.  This has the advantage of letting you open a sub-session and examine the results up to that point.  For example, in a separate cell enter:

    Flatten @ result // Short

And use <kbd>F7</kbd> to show the results, then resume calculation.

The `Monitor` lets you see how many blocks have been processed.