Số nguyên tố ghép
Xem dạng PDF
Gửi bài giải
Điểm:
0,13 (OI)
Giới hạn thời gian:
3.0s
Giới hạn bộ nhớ:
512M
Input:
stdin
Output:
stdout
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Xét dãy ~A~ các số nguyên tố ~2~, ~3~, ~5~, ~7~, ~11~, ~13~, ~17~, ~19~, ...và dãy ~B~ gồm các số thu được từ dãy ~A~ bằng cách ghép hai số liên tiếp trong ~A~: ~23~, ~57~, ~1113~, ~1719~, ... Trong dãy ~B~ có những phần tử là số nguyên tố. Chẳng hạn ~23~, ~3137~, ~8389~, ~157163~ ...
Các số nguyên tố trong dãy ~B~ gọi là số nguyên tố ghép.
Yêu cầu: Cho trước số nguyên dương ~K \leq 500~, hãy tìm số nguyên tố ghép thứ ~K~.
Input
- Gồm ~1~ số nguyên dương ~K~ duy nhất.
Output
- In ra ~1~ số nguyên dương duy nhất là số nguyên tố ghép thứ ~K~.
Sample Input
2
Sample Output
3137
Bình luận
include<bits/stdc++.h>
using namespace std; const int t=15000000; vector<bool> prime(t+5,true); vector<long long> a; void kt() { prime[0]=prime[1]=false; for(int i=2;i<=t/i;i++) { if(prime[i]) { for(int j=ii;j<=t;j+=i) prime[j]=false; } } for(int i=2;i<=t;i++) { if(prime[i]) a.push_back(i); } } bool isPrime(long long n) { if(n<2) return false; if(n==2||n==3) return true; if(n%2==0||n%3==0) return false; for(int i=5;i<=n/i;i+=6) { if(n%i==0||n%(i+2)==0) return false; } return true; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int k; cin >> k; kt(); int t=0; for(int i=0;i<a.size()-1;i+=2) { long long temp = a[i]; long long res = a[i+1]; while(res>0) { res/=10; temp=10; } long long s = temp+a[i+1]; if(isPrime(s)) { t++; if(t==k) { cout << s; return 0; } } } return 0; }
trick lỏ
nếu bí quá : gợi ý : click
solution ma quỷ vl :Đ
Gợi ý: click