Problem $1.$

Let $L$ be a sequence of numbers. We say that $L$ is primish if the sum of every two consecutive

elements in $L$ is a prime. For example, $L=\{1,6,7,4,13\}$ is primish since $1+6,6+7,7+4,$ and

$4+13$ are all prime numbers.

Design an algorithm that receives a sequence $L$ of integers and returns the length of the longest

primish subsequence. As usual, the numbers in the subsequence do not have to appear

consecutively in $L,$ but their order may not change. For example, when $L=\{1,2,5,8,2,7,11\}$

then a longest primish subsequence is $\{1,2,5,2,11\}.$

You must use dynamic programming. Assume that you can check if a number is prime in $O(1)$

time. The running time should be $O(n^2).$