| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P203PROH - Chuỗi nguyên tố |
Minduk là một người rất yêu thích số nguyên tố. Anh ta định nghĩa rằng : “Một chuỗi số nguyên được gọi là chuỗi nguyên tố nếu như số lượng số nguyên tố trong đó lớn hơn hoặc bằng số lượng số còn lại”.
Ví dụ: (1,3,2,6) là một chuỗi nguyên tố và (4,9,2,6) thì không phải.
Bạn được cung cấp một chuỗi số nguyên a gồm n số. Hãy giúp Minduk đếm số cặp (l,r) ( 1 ≤ l ≤ r ≤ n ) sao cho chuỗi con (al , al+1 , ..... ar ) là một chuỗi nguyên tố.
Input:
- Dòng đầu tiên là một số nguyên n (1 ≤ n ≤ 105).
- Dòng tiếp theo gồm n số nguyên ai (1 ≤ ai ≤ 106).
Output:
- Một dòng duy nhất chứa số lượng chuỗi nguyên tố.
Examples
|
Input |
Output |
|
3 1 3 4 |
3 |
|
4 1 3 5 7 |
9 |
| Được gửi lên bởi: | adm |
| Ngày: | 2020-08-29 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM64 CPP CPP14 JAVA PYTHON PYTHON3 |
