Nguồn đề bài: http://www.spoj.com/PTIT/problems/P134SUMF/
Nội dung bài viết
1. Đề bài P134SUMF spoj PTIT
Tí và Tèo đang cùng nhau học về sàng nguyên tố Eratosthenes.
Thuật toán sàng nguyên tố để tìm các số nguyên tố từ 2 tới N như sau:
1. Viết tất cả các số nguyên từ 2 tới N theo đúng thứ tự.
2. Tìm số nguyên nhỏ nhất chưa bị gạch. Gọi số đó là P. P sẽ là số nguyên tố.
3. Gạch bỏ P và tất cả các bội của nó.
4. Nếu tất cả các số chưa bị gạch bỏ, quay lại bước 2.
Tí đố Tèo rằng, cho trước N và K, hãy tìm số thứ K sẽ bị gạch bỏ.
Input
Chứa 2 số nguyên N và K (2 ≤ K < N ≤ 1000).
Output
Hãy in ra số thứ K sẽ bị gạch bỏ.
Example
Test 1:
Input:
7 3
Output:
6
Test 2:
Input:
15 12
Output:
7
Test 3:
Input:
10 7
Output:
9
Giải thích test 3: Các số lần lượt bị gạch bỏ sẽ là 2, 4, 6, 8, 10, 3, 9, 5, 7.
Do đó số thứ 7 sẽ là 9.
2. Code tham khảo P134SUMF spoj PTIT
Áp dụng thuật toán sàng nguyên tố Eratosthenes bình thường, 😀 còn lại thì đếm là được.
a. Code pascal
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 | const fi=''; nmax=1000; type data=longint; var f:text; x,M:data; A:array[1..nmax] of boolean; procedure xuli; var i,j,k:data; begin for i:=1 to x do a[i]:=false; i:=2; k:=0; while i<=x do begin if not a[i] then begin for j:=1 to x div i do if not a[i*j] then begin inc(k); if k=m then begin writeln(i*j); exit; end; a[i*j]:=true; end; end; inc(i); end; end; begin assign(f,fi); reset(f); while not eof(f) do begin readln(f,x,m); xuli; end; end. |
b. Code c++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | #include<stdio.h> #include <cmath> #include <iostream> using namespace std; int main() { int i,j,*a,k,count=0,n; cin >> n >> k; a=new int[n+1]; for(i=2;i<=n;i++) a[i]=1; for(i=2;i<=n/2;i++) for(j=1;j<=n/i;j++) { if(a[i*j]==1) //nếu là số chưa xử lý thì xóa đến hết n số { a[i*j]=0; count++; if(count==k) cout << i*j; } } } |
Bài viết liên quan
- Giải đề ACM PTIT round 3 2015
- BCPRIME PTIT spoj – Kiểm tra số nguyên tố
- PTIT016E spoj PTIT – ACM PTIT 2016 E – Kỳ thi ACM/ICPC
- P156SUME spoj PTIT – ROUND 6E – Ước chung của chuỗi
- P156SUMH spoj PTIT – ROUND 6H – Kim cương
- BCACM11D spoj PTIT – Đường nguyên tố
- TWO Spoj – Lập lịch trên hai máy
- PTIT127C spoj ptit- Bố trí phòng họp
- PTIT013K spoj PTIT – SỐ NGUYÊN HỆ CƠ SỐ ACM
- PTIT013A spoj PTIT – Số may mắn
Sao i không chạy đến sqrt(x) vậy ad.em vẫn chưa hiểu