[Python_Training] Sàng nguyên tố
Xem PDF
Điểm:
100 (p)
Thời gian:
1.5s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Bạn có một số nguyên dương \(N\). Nhiệm vụ của bạn là xuất ra tất cả các số nguyên tố từ \(1\) tới \(N\).
Input
- Gồm một dòng duy nhất chứa số nguyên \(N\) (\(N \leq 10^6)\).
Output
- Xuất ra tất cả các số nguyên tố từ \(1\) tới \(N\) trên cùng một dòng và cách nhau một dấu cách.
Example
Test 1
Input
10 Output
2 3 5 7
Bình luận
này là lỗi j vậy mọi người
HINT
Bài này anh em dùng sàng nguyên tố vẫn ac
sàng atkin ac ae ơi :)))
tại sao tôi vẫn k acp được :'))
tôi đã dùng đến tận miller rồi cơ mak :'))
ai cho tôi cách nào có thể chạy được đi :'))
Ơ KÌA AD
SAO NÓ KHÔNG XUỐNG DÒNG VẬY
đây là ý tưởng của tôi tuy vẫn còn thiếu sót nhưng nó cũng khá ổn
đầu tiên là tôi cho 1 hàm kiểm tra xem số đó có chia hết cho 2 3 5 7 hay không và đồng thời cũng kiểm tra xem số đó có phải là số chính phương hay không
nếu có thì return 0
ngược lại trả về 1
đây là code kiểm tra của tôi
-----------------------------------------------------------------------------
**
def nt1(a):
**
-----------------------------------------------------------------------------
ở đây tôi không return k ngay sau khi kiểm tra xem nó có chia hết cho các số kia hay không vì vẫn còn 1 trường hợp là nó chính là các số bị chia dùng để kiểm tra nó :'))
tiếp theo đó
tôi lại xây dựng thêm 1 hàm kiểm tra số nguyên tố tiếp
nhưng ở đây là các số lẻ
hàm kiểm tra này có lẽ nhiều người cũng biết rồi nên tôi chỉ nói sơ qua thôi
Tôi cho chạy từ 3 cho tới căn bậc 2 của n+1 rồi kiểm tra xem nếu có số nào chia hết cho nó thì return 0 ngay tại chỗ
còn không thì return 1 khi hết vòng lặp
ĐÂY LÀ CODE CỦA TÔI
-----------------------------------------------------------------------------------------
**
def nt2(a):
**
cho những ai chưa biết thì hàm ceil ở đây là tìm 1 số nhỏ nhất không nhỏ hơn x
mn có thể hiểu là nếu n là int thì ceil(n) vẫn sẽ bằng n
nếu n là float và int(n)!=float(n) thì ceil(n)=int(n)+1
ví dự như này nha
NHƯ VẬY MN HIỂU RỒI CHỨ
-----------------------------------------------------------------------------------------
Ở đây tôi không cần kiểm tra nó có bé hơn 1 hay không vì điều này ở đây là vô nghĩa (đề bài yêu cầu xuất số nt từ 1 tới n và đồng nghĩa với việc không có số âm)
sau đó
tôi xuất 2 ra với tất cả n>=2
theo đó
tôi chỉ cần 1 vòng lặp chạy các phần tử lẻ từ 3 tới n+1 và chạy 2 đơn vị
(tại sao ở đây tôi lại phải tăng n thêm 1 đơn vị???)
mọi người chắc cũng biết vòng for trong python chỉ chạy tới n-1 nếu cho giới hạn là n
tôi phải tăng thêm 1 đơn vị để tính luôn cả n vào trong vòng lặp (vì yêu cầu của đề là có tính luôn cả n)
đây là CODE HOÀN CHỈNH CỦA TÔI
----------------------------------------------------------------------------------------------------------
**
from sys import stdin
**
------------------------------------------------------------------------------------------------------------
có lẽ sẽ có 1 số người thắc mắc là tại sao tôi không xuất luôn ngay khi tìm thấy mà lại cho vào mảng rồi lại xuất cái mảng đó ra
thực ra tôi đã so sánh về thời gian khi chạy của cả 2 cách trên
nếu tôi thực hiện tìm được số nào thì xuất luôn ngay tại chỗ thì ưu điểm của nó là nó sẽ không tốn nhiều bộ nhớ như cách dùng mảng
nhưng vấn đề là thời gian
tuy dùng mảng sẽ tốn nhiều dữ liệu hơn nhưng ưu điểm của nó là nó sẽ có thời gian chạy nhanh hơn so với khi xuất ngay tại chỗ khi tìm được
VỚI CÁCH LÀM NÀY CỦA TÔI THÌ NÓ CŨNG CHỈ ĂN ĐƯỢC 12/14 TEST THÔI
MONG MỌI NGƯỜI HÃY GIÚP TÔI CÓ THÊM ĐƯỢC NHỮNG Ý KIẾN CHO ĐOẠN CODE NÀY ĐƯỢC HOÀN CHỈNH VÀO 1 NGÀY GẦN NHẤT
TÔI XIN CẢM ƠN ヾ(•ω•`)o
ai chỉ tôi các acp test cuối đi
k ac đc 2 test cuối là sao nhờ :'))
TLE nguyên bài =)))))