Trang 1 trên tổng số 2 12 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 12 kết quả

Đề tài: Tìm số tất cả các số nguyên tố có 5 chữ sô

  1. #1
    Ngày gia nhập
    08 2011
    Bài viết
    2

    Red face Tìm số tất cả các số nguyên tố có 5 chữ sô

    cô giáo mình vừa ra 1 bài tập

    Bài 1. Hãy liệt kê tất cả các số nguyên tố có 5 chữ số sao cho tổng số các chữ số trong số
    nguyên tố đó đúng bằng S cho trước 1≤S≤45.
    ----cùng thảo luận và cho mình nhiều cách giải nhé---

  2. #2
    Ngày gia nhập
    11 2010
    Nơi ở
    hell
    Bài viết
    154

    vừa duyệt kiểm tra xem pải snt ko rùi tính tổng s chứ pít seo jờ
    HT117-5277

  3. #3
    Ngày gia nhập
    10 2011
    Bài viết
    549

    Uẩy, vừa số nguyên tố vừa tính tổng chữ số ah
    Giải thuật là thế này :
    Viết 2 cái hàm kiểm tra nguyên tố và cái hàm tính tổng chữ số của 1 số
    Cho i chạy trên miền 10001 -> 99997
    Gọi 2 hàm ra coi thỏa ko, nếu thỏa thì in số i ra ngoài xem.
    _____
    Mới ở mức độ này thì cứ làm cái việc trên cho nó OK đã
    Làm dc rồi thì nghĩ tiếp chuyện "tối ưu" . Ví dụ như nhập S=45 hoặc S=1 thì khỏi cần phải kiểm tra gì sất, vì ko có số nào thỏa đâu mà chạy cho mệt ^^(tuy nhiên nếu cứ cho chạy cũng ko sao )
    Rồi còn 1 số ước lượng liên quan nữa làm sao cho Ta kiểm tra hàm này trước hay hàm kia trước sẽ cho tốc độ nhanh. Rồi cho S như này thì ta chỉ cần cho chạy trên miền này, cho S như kia thì chỉ cần chạy trên miền kìa ... blah blah ^^
    Đã được chỉnh sửa lần cuối bởi clchicken : 12-01-2012 lúc 06:13 PM.
    Um Mani Padme Hum...!!

  4. #4
    Ngày gia nhập
    11 2010
    Bài viết
    578

    Với những bài này thì có thể dùng sàng số nguyên tố. Có thể tốn kha khá bộ nhớ (1MB) nhưng chạy nhanh.
    http://vi.wikipedia.org/wiki/Số_nguy...ng_Eratosthene

  5. #5
    Ngày gia nhập
    10 2011
    Bài viết
    549

    Hahahaha, để mình bày cho cách này chọc cô giáo cho vui nè ).
    Đầu tiên là tìm toàn bộ những số nguyên tố có 5 chữ số , in chúng ra 1 nơi nào đấy (giấy chẳng hạn). Miễn sao ta nắm dc trong tay toàn bộ những số này

    Rồi đến file code bài tập này. Viết 1 đoạn code mới hoàn toàn (code này giờ ko đụng gì đến số nguyên tố cả, ko có mùi số nguyên tố ở đây)
    Làm 1 cái mảng khởi tạo các số mà ta vừa viết ra vừa rồi. (Ko liên quan gì đến cái công đoạn ta tìm ta các số nguyên tố cả
    Sau đó chỉ việc kiểm tra tổng chữ số của nó có = S hay ko là xuất ra thôi =)). Cô đọc vào đảm bảo té ngửa nhưng ko thể cho bạn thấp điểm dc bởi vì nó đúng hoàn toàn
    Bảo cô còn nghi ngờ gì thì cứ test thoải mái =))
    Đã được chỉnh sửa lần cuối bởi clchicken : 12-01-2012 lúc 07:49 PM.
    Um Mani Padme Hum...!!

  6. #6
    Ngày gia nhập
    01 2012
    Nơi ở
    localhost
    Bài viết
    56

    Cool Tìm số tất cả các số nguyên tố có 5 chữ sô

    Trích dẫn Nguyên bản được gửi bởi clchicken Xem bài viết
    Hahahaha, để mình bày cho cách này chọc cô giáo cho vui nè ).
    Đầu tiên là tìm toàn bộ những số nguyên tố có 5 chữ số , in chúng ra 1 nơi nào đấy (giấy chẳng hạn). Miễn sao ta nắm dc trong tay toàn bộ những số này

    Rồi đến file code bài tập này. Viết 1 đoạn code mới hoàn toàn (code này giờ ko đụng gì đến số nguyên tố cả, ko có mùi số nguyên tố ở đây)
    Làm 1 cái mảng khởi tạo các số mà ta vừa viết ra vừa rồi. (Ko liên quan gì đến cái công đoạn ta tìm ta các số nguyên tố cả
    Sau đó chỉ việc kiểm tra tổng chữ số của nó có = S hay ko là xuất ra thôi =)). Cô đọc vào đảm bảo té ngửa nhưng ko thể cho bạn thấp điểm dc bởi vì nó đúng hoàn toàn
    Bảo cô còn nghi ngờ gì thì cứ test thoải mái =))
    Không ổn. Cô chấm source mà
    Rẹt rẹt..

  7. #7
    Ngày gia nhập
    10 2011
    Bài viết
    549

    Sao lại ko ổn?
    Code đó giải quyết toàn bộ bài toán mà. Đâu có giải sai chỗ nào đâu ?
    Chấm source hay chấm gì cũng thế thôi
    Um Mani Padme Hum...!!

  8. #8
    Ngày gia nhập
    03 2009
    Nơi ở
    %appdata%\Temp
    Bài viết
    819

    Sao không ai nghĩ đến cách này nhỉ, có vẻ nhanh hơn.
    1. Tìm tất cả các số có 5 chữ số có tổng bằng S (giải phương trình nghiệm nguyên dương bằng quay lui vét cạn)
    2. Kiểm trả các số tìm được có phải là số nguyên tố không bằng cách:
    a. Dùng sàng eratosthene tìm tất cả những số nguyên tố nhỏ hơn hoặc bằng sqrt(99999) lưu vào một mảng.
    b. Nếu số nào không chia hết cho tất cả các số chứa trên mảng trên thì là số nguyên tố.

    PS: Ngoài ra có thể thêm vào 1 số đánh giá, ví dụ nếu S chia hết có 3 thì có thể khẳng định luôn không có kết quả nào
    .::[The best way to predict the future is to invent it]::.
    __________________________________________________ _ - Alan Kay -

  9. #9
    Ngày gia nhập
    01 2012
    Nơi ở
    localhost
    Bài viết
    56

    PS: Ngoài ra có thể thêm vào 1 số đánh giá, ví dụ nếu S chia hết có 3 thì có thể khẳng định luôn không có kết quả nào
    Có số 3
    Nếu đã dùng sàng Eratosthene thì mình để phần kiểm tra tổng S sau có vẻ đỡ hơn là quay lui vét cạn (tàu ráo máng)

    Đây là ý tưởng của mình dựa trên những ý tưởng của các bạn:
    1. Tìm tất cả các số nguyên tố từ 1 tới 99999 theo cách: chia lần lượt số đang xét (giả sử là X) cho các số nguyên tố bé hơn hoặc bằng căn bậc 2 của X. Nếu X không chia hết cho số nào cả thì X là số nguyên tố.
    2. Bắt đầu từ X = 10000 trở đi, nếu phát hiện X là số nguyên tố thì mình tính tổng các số thành phần và so sánh với S. Nếu bằng thì xuất ra màn hình. Tiếp tục xét tiếp.
    ~Happy coding :P
    Rẹt rẹt..

  10. #10
    Ngày gia nhập
    03 2009
    Nơi ở
    %appdata%\Temp
    Bài viết
    819

    Ai cũng biết kiểm tra số nguyên tố tốn kém hơn là việc kiểm tra xem tổng các chữ số của số đó có bằng S không, vì thế nên làm hẹp tập cần kiểm tra trước, có nghĩa là ta sẽ duyệt từ 10000 đến 99999 kiểm tra tổng xem có bằng S trước không rồi mới kiểm tra số nguyên tố.
    Kiểm tra số nguyên tố thì như mình đã nói ở trên. Bằng đánh giá rằng tất cả các ước số nguyên tố của một số có 5 chữ số đều nhỏ hơn hoặc bằng sqrt(99999) nên ta tìm tất cả các số nguyên tố nhỏ hơn sqrt(99999) trước làm đầu vào
    .::[The best way to predict the future is to invent it]::.
    __________________________________________________ _ - Alan Kay -

Các đề tài tương tự

  1. Bài tập C giải thuật nhập vào số nguyên n in ra n số nguyên tố đầu tiên?
    Gửi bởi LTC trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 48
    Bài viết cuối: 25-04-2013, 07:40 PM
  2. Viết chương trình nhập số nguyên dương n, liệt kê n số nguyên tố đầu tiên.
    Gửi bởi maiit trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 11
    Bài viết cuối: 19-06-2011, 01:05 PM
  3. Game Viết chương trình nhập số nguyên dương n, liệt kê n số nguyên tố đầu tiên trên C#?
    Gửi bởi maiit trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 18
    Bài viết cuối: 08-06-2011, 11:12 PM
  4. Bài tập C++ chương trình đổi 1 số nguyên trong hệ thập phân sang hệ fibo và cộng 2 số nguyên được
    Gửi bởi nghiapro512 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 3
    Bài viết cuối: 23-01-2011, 02:14 PM
  5. Lập trình C xin code cài đặt thuật toán sàng nguyên tố để liệt kê các số nguyên tố 2->480000
    Gửi bởi ngocdung_088 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 23
    Bài viết cuối: 06-12-2010, 11:53 PM

Tags của đề tài này

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn