ctc10-Hàm nguyên tố
Xem dạng PDF
Gửi bài giải
Điểm:
100,00 (OI)
Giới hạn thời gian:
0.55s
Giới hạn bộ nhớ:
256M
Input:
FUNCPRIME.INP
Output:
FUNCPRIME.OUT
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch
Hàm nguyên tố
Tên file: funcprime.*
Ta định nghĩa hàm: ~f(x)~ = tổng các số nguyên tố nhỏ hơn hoặc bằng ~x~.
Ví dụ: ~f(4) = 2 + 3 = 5; f(7) = 2 + 3 + 5 + 7 = 17~. Cho trước giá trị ~n~ nhập từ bàn phím. Hãy kiểm tra ~f(n)~ có phải là một số nguyên tố không?
Input:
Giá trị n nhập từ bàn phím (~1 ≤ n ≤ 100000~)
Output:
Thông báo YES nếu ~f(n)~ là số nguyên tố, thông báo NO trong trường hợp ngược lại.
Ví dụ:
| FUNCPRIME.INP | FUNCPRIME.OUT |
|---|---|
| 5 | NO |
| 7 | YES |
Bình luận
include <bits/stdc++.h>
using namespace std; bool nt[10000007]; void sang(){ memset(nt, 1, sizeof(nt)); nt[0] = nt[1] = 0; for (int i = 2; i <= sqrt(1e7); i++){ for (int j = i * i; j <= 1e7; j += i){ nt[j] = 0; } } } int main(){ sang(); long long n; cin >> n; long long s = 0; for (int i = 2; i <= n; i++){ if (nt[i]){ s += i; } } if (nt[s]) cout << "YES"; else cout << "NO"; return 0; }
cho xem code bài này với