primeAndComposite

Ta định nghĩa:

• Số nguyên tố là số nguyên tự nhiên lớn hơn 1, chỉ chia hết cho 1 và chính nó.
• Hợp số là số dương mà không phải là số nguyên tố.

Yêu cầu: Cho một mảng chứa các số nguyên dương A. Hãy đếm xem có bao nhiêu số cặp (l, r) mà 0 <= l <= r < A.size() thỏa mãn điều kiện số lượng số nguyên tố trong khoảng từ A[l] -> A[r] lớn hơn hoặc bằng số lượng hợp số trong khoảng từ A[l] -> A[r].

Ví dụ: 

• A = [1,2,3,5] thì countPair(A) = 9
  Giải thích: Với mảng A được cho, các cặp (l, r) thỏa mãn điều kiện yêu cầu đưa ra là:
  • (0,1) tương ứng với A[0] = 1, A[1] = 2, trong khoảng này ta sẽ có 1 số nguyên tố là 2 và 1 hợp số là 1.
  • (0,2) tương ứng với A[0] = 1 , A[1] = 2, A[2] = 3, trong khoảng này ta sẽ có 2 số nguyên tố là 2, 3 và 1 hợp số là 1.
  • (0,3) tương ứng với A[0] = 1, A[1] = 2,  A[2] = 3, A[3] = 5, trong khoảng này ta sẽ có 3 số nguyên tố là 2, 3, 5 và 1 hợp số là 1.
  • (1,1) tương ứng với A[1] = 2, trong khoảng này ta sẽ có 1 số nguyên tố là 2 và không có hợp số nào.
  • (1,2) tương ứng với A[1] = 2, A[2] = 3, trong khoảng này ta sẽ có 2 số nguyên tố là 2, 3 và không có hợp số nào.
  • (1,3) tương ứng với A[1] = 2, A[2] = 3, A[3] = 5, trong khoảng này ta sẽ có 3 số nguyên tố là 2, 3, 5 và không có hợp số nào.
  • (2,2) tương ứng với A[2] = 3, trong khoảng này ta sẽ có 1 số nguyên tố là 3 và không có hợp số nào.
  • (2,3) tương ứng với A[2] = 3, A[3] = 5, trong khoảng này ta sẽ có 2 số nguyên tố là 3, 5 và không có hợp số nào.
  • (3,3) tương ứng với A[3] = 5, trong khoảng này ta sẽ có 1 số nguyên tố là 5 và không có hợp số nào.

Đầu ra/Đầu vào

• [Giới hạn thời gian chạy] 0.5s với C++, 3s với Java/C#, 4s với Python,Js, Go
• [Đầu vào] array.integers A
  1 <= A.size() <= 105
1 <= A[i] <= 106
• [Đầu ra] long
  Số cặp (l,r) thỏa mãn yêu cầu của bài toán.