昨日の「最小の約数を探す」部分を別関数にして工夫したら、かなり改善しました。依然、大きな素数だと結果が出るまで遅いですが。実行環境は昨日と同じWindows版PostgreSQL 9.5.3、Core i5-3320M（2.6GHz）です。

with recursive arg (num) as (
    select 2.0^50 - 1  -- a number of interest (within int8)
), rec (num, factors) as (
    select num :: int8, null :: int8[] from arg
    union all
    select num / ff, factors || ff
    from rec,
        first_factor(num, factors[ array_length(factors, 1) ]) as ff 
    where ff is not null
)
select * from rec;
+------------------+------------------------+
|       num        |        factors         |
+------------------+------------------------+
| 1125899906842623 |                        |
|  375299968947541 | {3}                    |
|   34118178995231 | {3,11}                 |
|    1100586419201 | {3,11,31}              |
|       4384806451 | {3,11,31,251}          |
|          7295851 | {3,11,31,251,601}      |
|             4051 | {3,11,31,251,601,1801} |
+------------------+------------------------+
(7 rows)
Time: 0.000 ms


↑ の2.0^50 - 1の素因数分解に、昨日は7秒もかかってました。最小の約数を見つける部分を、常に「対象数の平方根までgenerate_seriesで1個ずつ列挙」と手抜きだったため。今日は ↓ こんな関数に外部化し、generate_seriesでなく再帰クエリで値を2ずつ増やして（2以外の偶数をスキップ）探索してます。
create or replace function first_factor(int8, int8 default null)
returns int8 language sql immutable as
$$
with recursive rec (num, fcand, max) as (
    select $1, coalesce($2, 2), floor(sqrt($1)) :: int8
    union all
    select num, fcand + case when fcand = 2 then 1 else 2 end, max 
    from rec
    where fcand <= max
)
select fcand from rec where num % fcand = 0 limit 1;
$$;

-- test
select first_factor( (2.0^50 - 1) :: int8 );
+--------------+
| first_factor |
+--------------+
|            3 |
+--------------+
(1 row)
Time: 1.000 ms

select first_factor( (2.0^59 - 1) :: int8);
+--------------+
| first_factor |
+--------------+
|       179951 |
+--------------+
(1 row)
Time: 97.013 ms


↑ 最小の約数が179951と大きい場合、100ミリ秒程度かかってます。逆に小さい約数を多く含む数、例えば2^52 - 1だと ↓ 短時間で次々に約数が見つかって数値が分解され、一瞬で終了。
with recursive arg (num) as (
    select 2.0^52 - 1
), rec (num, factors) as (
    select num :: int8, null :: int8[] from arg
    union all
    select num / ff, factors || ff
    from rec,
        first_factor(num, factors[ array_length(factors, 1) ]) as ff 
    where ff is not null
)
select * from rec;
+------------------+------------------------+
|       num        |        factors         |
+------------------+------------------------+
| 4503599627370495 |                        |
| 1501199875790165 | {3}                    |
|  300239975158033 | {3,5}                  |
|    5664905191661 | {3,5,53}               |
|      36082198673 | {3,5,53,157}           |
|         22369621 | {3,5,53,157,1613}      |
|             8191 | {3,5,53,157,1613,2731} |
+------------------+------------------------+
(7 rows)
Time: 0.000 ms


↓ 素数でない数で非常に時間かかった例。2^62 - 1とINT8上限に近い大きな数で約400秒。最初に3で割れた後、その商1537228672809129301の約数がなかなか見つからず、こんな結果になりました。
with recursive arg (num) as (
    select 2.0^62 - 1
), rec (num, factors) as (
    select num :: int8, null :: int8[] from arg
    union all
    select num / ff, factors || ff
    from rec,
        first_factor(num, factors[ array_length(factors, 1) ]) as ff 
    where ff is not null
)
select * from rec;
+---------------------+---------------+
|         num         |    factors    |
+---------------------+---------------+
| 4611686018427387903 |               |
| 1537228672809129301 | {3}           |
|          2147483647 | {3,715827883} |
+---------------------+---------------+
(3 rows)
Time: 397070.922 ms


大きい素数だと最後まで約数が見つからず延々続くので ↓ こんな風にもっと時間がかかります。2^61 - 1で850秒…。
with recursive arg (num) as (
    select 2.0^61 - 1
), rec (num, factors) as (
    select num :: int8, null :: int8[] from arg
    union all
    select num / ff, factors || ff
    from rec,
        first_factor(num, factors[ array_length(factors, 1) ]) as ff 
    where ff is not null
)
select * from rec;
+---------------------+---------+
|         num         | factors |
+---------------------+---------+
| 2305843009213693951 |         |
+---------------------+---------+
(1 row)
Time: 850515.002 ms


↓ 素数でも32ビット符号つき整数くらいまでなら、昨日と同じで10数ミリ秒。この先に大きな壁がある感じですが、少しでも改善できたら再追記します。
with recursive arg (num) as (
    select 2^31 - 1
), rec (num, factors) as (
    select num :: int8, null :: int8[] from arg
    union all
    select num / ff, factors || ff
    from rec,
        first_factor(num, factors[ array_length(factors, 1) ]) as ff 
    where ff is not null
)
select * from rec;
+------------+---------+
|    num     | factors |
+------------+---------+
| 2147483647 |         |
+------------+---------+
(1 row)
Time: 15.600 ms