Trang ChínhTrang Chính  CalendarCalendar  Trợ giúpTrợ giúp  Tìm kiếmTìm kiếm  Thành viênThành viên  NhómNhóm  Đăng kýĐăng ký  Đăng NhậpĐăng Nhập  
News & Announcements
  • Top posters
 Mr.Pakapun (256)
 ddtan90 (178)
 tvduong (147)
 dthnam90 (137)
 minhquankq (101)
 arianbo (70)
 DoanhNhan (54)
 chicken (53)
 stormit (52)
 gentle_storm (47)

Share | 
 

 Sàn lọc số nguyên tố

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down 
Tác giảThông điệp
ddtan90
Admin
Admin
avatar

Tổng số bài gửi : 178
Join date : 30/12/2010
Age : 26
Đến từ : SE 3 - K34

Bài gửiTiêu đề: Sàn lọc số nguyên tố   Sat Jan 08, 2011 12:26 am

Toàn bộ số tự nhiên được chia làm ba loại: Loại 1 là các số nguyên tố ( như 2,3,5,7,11,13,…), Loại 2 là các hợp số ( 4,6,8,9,10,…) . Số “1″ không phải là số nguyên tố, cũng không phải là hợp số nên nó là một loại riêng thứ 3. Số nguyên tố là những số chỉ chia hết cho 1 và chính nó, còn hợp số có thể chia hết cho những số khác.
Trong một số bài toán yêu cầu cần xác định một số có phải là số nguyên tố không! Ví dụ như bài toán tìm thừa số nguyên tố của 1 dãy n số tự nhiên cho trước chẳng hạn. giả sử n=10, các số trong dãy là 17, 56, 45, 78, 12876, 998756, 1967, 567,1299907767, 34435343.
Cách thông thường là tại mỗi số, cho vòng lặp i chạy từ 2 đến căn bậc 2 của số đó rồi kiểm tra xem i có phải là số nguyên tố hay không bằng 1 vòng lặp khác nữa. Như vậy rất mất thời gian.
Có một cách nhanh hơn. Trước tiên chúng ta sẽ tạo ra một sàn nguyên tố ngay từ đầu. Khi cần xác định 1 số có phải là nguyên tố hay không chỉ cần 1 bước so sánh thôi.

Sàn nguyên tố thực ra là 1 mảng nguyento kiểu bool. Đầu tiên cho tất cả các phần tử có giá trị true.
Sau đó, chúng ta sẽ đánh dấu mảng tại vị trí những số nào không là số nguyên tố thành false. Những vị trí còn giá trị true thì sẽ là số nguyên tố.
Khi cần so sánh 1 số r có phải là nguyên tố hay không, chúng ta chỉ cần gọi (nguyento[r]==true).

Code demo:


Code:

//gia su trong bai nay minh hci xet den 1000
bool nguyento[1000];
for (int i=0;i<1000;i++) nguyento[i]=true;

nguyento[0]=nguyento[1]=false; //0 va 1 khong la so nguyen to

for (int i=2;i<sqrt(1000);i++)
    for (int j=2;j*i<1000;j++)
          nguyento[i*j]=false;

_____________________
Nothing is impossible!
Về Đầu Trang Go down
Xem lý lịch thành viên
RikoSairenji
Thành viên mới
Thành viên mới
avatar

Tổng số bài gửi : 5
Join date : 10/01/2011

Bài gửiTiêu đề: Re: Sàn lọc số nguyên tố   Thu Jan 13, 2011 2:05 pm

Mình không nghĩ cách của bạn nhanh hơn cách thông thường đâu. Cách của bạn có độ phức tạp O(n^2) thì không thể nhanh hơn cách cũ là O(n)
Về Đầu Trang Go down
Xem lý lịch thành viên
ddtan90
Admin
Admin
avatar

Tổng số bài gửi : 178
Join date : 30/12/2010
Age : 26
Đến từ : SE 3 - K34

Bài gửiTiêu đề: Re: Sàn lọc số nguyên tố   Thu Jan 13, 2011 9:32 pm

Đíng là cách của mình dùng trong trường hợp kiểm tra 1 số không nhanh hơn bình thường.
Nhưng mình đã có nói ngay từ đầu, trong trường hợp kiểm tra 1 chuỗi nhiều số để tìm ra những số nguyên tố chẳng hạn thì tố độ sẽ nahnh gấp rất nhiều lần.
Thay vì với mỗi phần tử bạn phải chạy sqrt (n) lần để kiểm tra phần tử n đó có phải là nguyên tố hay không theo cách thường thì lúc này bạn chỉ cần chạy 1 lần và sau đó kiểm tra từng phần tử chỉ bằng 1 phép so sánh. Chuỗi càng nhiều phần tử thì cách này lại cảng tỏ ra có hiệu quả. Những đề thi lập trình không bao giờ yêu cầu kiểm tra 1 phần tử mà rất nhiều phần tử, có khi đến hàng triệu!flower

Với lại mình xin đính chính lại, thuật toán đó không đến nỗi O(n^2) đâu. Cách tính độ phức tạp như thế nào thì mình không nhớ rõ nhưng 2 vong lặp đó không thể nào là O(n^2) được! Very Happy

_____________________
Nothing is impossible!
Về Đầu Trang Go down
Xem lý lịch thành viên
minhquankq
Mod
Mod
avatar

Tổng số bài gửi : 101
Join date : 05/01/2011
Age : 25
Đến từ : Đại học cần thơ

Bài gửiTiêu đề: Re: Sàn lọc số nguyên tố   Fri Jan 14, 2011 11:50 am

hi...Cái tính độ phức tạp vừa mới học...quá tính sơ sơ ban đầu thì hình như kết quả là tổng (1000/i - 2) i chạy từ 2 đến căn bật 2 của n....
(tại không bt vẽ cái sít ma lên trên này... Laughing

_____________________
Đây là thời đại nào rồi nhỉ Shocked
Về Đầu Trang Go down
Xem lý lịch thành viên http://AloneWithMe.co.cc
Sponsored content




Bài gửiTiêu đề: Re: Sàn lọc số nguyên tố   

Về Đầu Trang Go down
 
Sàn lọc số nguyên tố
Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang 
Trang 1 trong tổng số 1 trang
 Similar topics
-
» Xuất phát đi Tây Nguyên
» Các tiêu chuẩn đánh giá ổn định nguyên vẹn tàu
» Nguyên tắc đặt gương theo thuyết phong thủy
» [Fic nối]Học viện Tây Nguyên 3000 | Đăng kí |
» Phần mềm tính toán ổn định nguyên vẹn và sức bền dọc thân tàu

Permissions in this forum:Bạn không có quyền trả lời bài viết
Câu lạc bộ Hỗ Trợ Học Tập :: LẬP TRÌNH :: .::LẬP TRÌNH C/C++-
Chuyển đến