완전한 수열

면접 대비

시간 제한1초메모리 제한1024 MB

요약

길이와 합이 모두 소수인 연속 부분 수열의 개수를 구합니다.

문제

다음 두 조건을 모두 만족하는 수열을 완전한 수열이라고 한다.

어떤 수열의 연속 부분 수열 중에서 완전한 수열인 것의 개수를 그 수열의 안정도라고 한다.

정수로 이루어진 수열 $a_1,a_2,\cdots,a_N$ 이 주어진다.

이 수열의 안정도를 구한다.

첫째 줄에 정수 $N$ 이 주어진다. $(4\leq N \leq 500)$

둘째 줄에 정수로 이루어진 수열 $a_1,a_2,\cdots,a_N$ 이 공백으로 구분되어 주어진다. $(0\leq a_i \leq 2\,000)$

첫째 줄에 주어진 수열의 안정도를 출력한다.

소수는 2 이상의 양의 정수이면서, 1과 자기 자신 이외의 양의 약수를 갖지 않는 수이다.