Computer search solution.
It's easy to see that P and Q can't both contain an even number (since two positive even numbers never add up to a prime) or an odd number (since two distinct positive odd numbers don't either). We can therefore assume that P consists of just odd numbers and Q of just even numbers.
A quick and dirty Python script then identifies...
276 length 6 solutions but no length 7 ones. The first solution it gives is P=[1, 5, 11, 35, 71, 95] and Q=[2, 12, 18, 36, 78, 96]; the last is P=[15, 33, 39, 75, 93, 99] and Q=[4, 8, 14, 64, 74, 98].
Here is the script:
from sympy import isprime
solutions = []
def find_odd(odds, evens):
if len(odds) >= 6: solutions.append((odds, evens))
for o in range(odds[-1]+2 if odds else 1, 101, 2):
if not odds: print(f"\n{o: 2d} ", end="")
if all(isprime(o + e) for e in evens):
find_even(odds + [o], evens)
def find_even(odds, evens):
for e in range(evens[-1]+2 if evens else 2, 101, 2):
if not evens: print(".", end="")
if all(isprime(o + e) for o in odds):
find_odd(odds, evens + [e])
find_odd([], [])
Update. After a bit of thought, I realised there's a somewhat faster algorithm: you can precompute the compatible odd numbers for every even numbers and just loop through combinations of even numbers.
from sympy import isprime
def solve(N=100):
best = 0
odds = set(range(1,N+1,2))
compatible = { e : { o for o in odds if isprime(e+o) } for e in range(2,N+1,2) }
def find(evens, odds):
nonlocal best
if len(evens) > best:
best = len(evens)
print(evens, list(odds)[:best])
for e in range(evens[-1]+2 if evens else 2, N+1, 2):
compat_odds = odds & compatible[e]
if len(compat_odds) > len(evens):
find(evens+[e], compat_odds)
find([], odds)
Which gives:
>> solve(100)
[2] [1]
[2, 4] [1, 3]
[2, 4, 8] [99, 3, 39]
[2, 4, 8, 14] [3, 99, 39, 9]
[2, 4, 8, 14, 28] [99, 3, 39, 9, 15]
[2, 4, 14, 28, 58, 98] [3, 99, 69, 39, 9, 15]
>> solve(420)
[2] [1]
[2, 4] [1, 3]
[2, 4, 8] [225, 3, 99]
[2, 4, 8, 10] [99, 9, 3, 189]
[2, 4, 8, 14, 28] [3, 99, 39, 9, 15]
[2, 4, 8, 14, 28, 64] [99, 3, 39, 9, 15, 345]
[2, 4, 8, 22, 44, 74, 88] [39, 9, 105, 15, 309, 345, 189]
[2, 4, 8, 44, 88, 158, 232, 452] [225, 39, 105, 9, 459, 309, 345, 189]
[12, 48, 90, 138, 168, 180, 300, 342, 420] [419, 101, 11, 179, 341, 89, 59, 221, 319]