Đếm số T-Prime
Xem dạng PDF
Gửi bài giải
Điểm:
20,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch
Số T-Prime là số nguyên dương có đúng 3 ước số nguyên dương khác nhau. Ví dụ 49 là số T-Prime vì 49 có đúng 3 ước số nguyên dương là 1, 7, 49.
Yêu cầu: Cho trước số nguyên dương ~N~ (~0 < N ≤ 10^6~) và dãy gồm ~N~ số nguyên dương ~a_1, a_2,...a_N~ (~0 \le a_i \le 10^{10}~). Hãy đếm xem có bao nhiêu số T-Prime trong dãy.
Dữ liệu vào:
- Dòng thứ nhất: Ghi số nguyên ~N~.
- Dòng 2: Ghi ~N~ số nguyên ~a_1, a_2,...a_N~
Dữ liệu ra:
- Một số nguyên duy nhất là kết quả của bài toán.
Ví dụ:
Input
8
3 4 5 9 36 49 55 121
Output
4
Bình luận
include <bits/stdc++.h>
using namespace std; bool hh(long long k) { if(k<2) return false; for (long long i=2;ii<=k;i++) { if (k%i==0) { return false; } } return true; } int main() { long long N; cin>>N; long long x=sqrt(N);if (xx==N&&hh(x)) {cout<<"Y"; }else {cout<<"N"; } return 0; }