Question
Prime Sum Subarrays
You are given an array KaTeX can only parse string typed expression of KaTeX can only parse string typed expression integers. You look at every continuous subarray of KaTeX can only parse string typed expression and calculate its sum. If the sum is a prime number, the subarray is considered good.
Your task is to count the number of good subarrays.
Input
The first line contains a single integer KaTeX can only parse string typed expression — the size of the array.
The second line contains KaTeX can only parse string typed expression integers — KaTeX can only parse string typed expression.
The second line contains KaTeX can only parse string typed expression integers — KaTeX can only parse string typed expression.
Output
Print a single integer — the number of subarrays whose sum is a prime number.
Example
Input
5
1 2 3 4 5
Output
6
Explanation
The subarrays with prime sum are:
(0, 1) → sum = 3
(1, 1) → sum = 2
(2, 2) → sum = 3
(4, 4) → sum = 5
(1, 2) → sum = 5
(2, 3) → sum = 7
So, the answer is 6.
5
1 2 3 4 5
Output
6
Explanation
The subarrays with prime sum are:
(0, 1) → sum = 3
(1, 1) → sum = 2
(2, 2) → sum = 3
(4, 4) → sum = 5
(1, 2) → sum = 5
(2, 3) → sum = 7
So, the answer is 6.