1. THÔNG BÁO TUYỂN ADMIN DIỄN ĐÀN 2013
    Tìm kiếm nhà trọ - Ở ghép
    THÔNG BÁO BÁN ÁO SPKT.NET CHO THÀNH VIÊN DIỄN ĐÀN


    HÃY TÌM KIẾM Ở ĐÂY TRƯỚC KHI ĐẶT CÂU HỎI
    {xen:phrase loading}

Hướng dẫn học lập trình C/C++ cho các bạn khoa ĐĐT

Thảo luận trong 'ĐT Cơ Bản-Mạch tương tự' bắt đầu bởi phoenix, 25 Tháng sáu 2009.

  1. phoenix Administrator

    Số bài viết: 633
    Đã được thích: 13
    Điểm thành tích: 0
    Số nguyên tố | Cách kiểm tra nhanh N có phải là số nguyên tố
    ài toán này đã trở nên rất đỗi quen thuộc với chúng ta, trong bài này chúng ta sẽ bàn đến cách kiểm tra 1 số nguyên N cho trước có nguyên tố hay không trong phạm vi kiến thức số học sơ cấp.

    Có rất nhiều cách, các cách thông thường là:
    + Xét các số từ 1 đến N xem có bao nhiêu số là ước của N rồi so sánh với 2. Cách này chạy rất chậm!
    + Xét các số từ 2 đến sqrt(N) rồi nếu là ước của N thì dừng lại, nhanh hơn 1 chút!

    Ta sẽ bàn 1 cách nhanh hơn nữa:
    Rõ ràng cái ta cần là làm sao giảm bớt số lượng số phải đem ra thử có phải là ước của N hay không. Trong danh sách này, có thể thừa (như 2 cách trên thừa rất nhiều) nhưng tuyệt đối không được thiếu các số nguyên tố bé hơn hoặc bằng sqrt(N). Vậy thì ta sẽ duyệt các số này theo 1 quy luật nào đó. Quy luật đó là gì?

    Nhận xét: 1 số nguyên tố chia cho 6 dư 1 hoặc 5 (dễ dàng chứng minh) suy ra tập các số nguyên chia 6 dư 1 hoặc 5 sẽ bao trùm tập các số nguyên tố.

    Từ đây ta có thuật toán: ta chỉ xét các số bé hơn hoặc bằng sqrt(N) mà chia 6 dư 1 hoặc 5 mà thôi, nếu N chia hết cho bất cứ 1 số nào trong đó thì N là hợp số, trái lại N là nguyên tố.

    không phải ngẩu nhiên mà tôi chọn hằng số k= 6 này. Bài toán trở thành tìm số k mà từ 1 tới k-1 có ít số nguyên tố cùng nhau với nó nhất. Khi đó tỉ lệ phải xét chính là tỉ số các số nguyên tố cùng nhau này với k

    thực nghiệm thì thấy số k tổng quát là tích của vài số nguyên tố đầu tiên, tất nhiên càng nhiều thì tỉ lệ phải xét càng nhỏ nhưng cài đặt có phần phức tạp hơn

    các bạn mới làm toán thì bỏ qua tìm số k này, giỏi lên một tí các bạn cho k=2 để loại các số chẳn
    rồi k=6 để loại các số chia hai huặc ba
    nếu k=2*3*5=30( tỉ lệ phải xét, 4/15) thì tốc độ đc cải thiện đáng để, bạn thử cài đặt nhé, chú ý cái đặt thế nào cho thông minh

    khi nghịch mã nguồn của Maple thì thấy nó lấy k là tích các số nguyên tố <1000 cơ
  2. tranphong2 Nothing

    Số bài viết: 273
    Đã được thích: 2
    Điểm thành tích: 0
    Ngôn ngữ thì tùy bạn lựa cho, nhưng theo mình bạn tự học thì nên học C, vì ASM liên quan nhiều đến phần cứng nên khó hiểu. Chọn được 1 ngôn ngữ rồi thì đi theo nó là phần mềm, nếu là C thì có thể dùng Keil C cho 8051, nếu là ASM thì dùng SPKT (của thầy Phú trường mình viết)...v.v

    Viết chương trình bằng mấy chương trình đó rồi biên dịch ra file Hex (file này để nạp cho con VDK)
    Về phần cứng thì có thể dùng chương trình Proteus để mô phỏng.
  3. tranphong05 New Member

    Số bài viết: 3
    Đã được thích: 0
    Điểm thành tích: 0
    Theo như Mumble nói thì mình tán thành học C. Nhưng kid_amater này, chường trình trong trường dạy bằng ASM đấy, không học là bạn sẽ gặp death đấy.
  4. kid_pro Member

    Số bài viết: 208
    Đã được thích: 6
    Điểm thành tích: 18
    có pro nào có tài liệu về ASM không send cho mình với. mình tự học ASM nhưng khó hiểu quá. mong các bạn giúp. xin cảm ơn
  5. Nguyen Quang New Member

    Số bài viết: 15
    Đã được thích: 0
    Điểm thành tích: 0

Chia sẻ trang này