Tìm số nguyên tố thứ 10001

Số nguyên tố không chỉ có không chia hết cho các số từ 1->9 đâu bạn.

Bạn xem cách kiểm tra nguyên tố ở đây nhé:

neihousaigaai/diễn đànWiki/blob/master/Algorithm/Math/prime-number/prime-number-algorithm.md

Chào mừng các bạn đến với mục Algorithm của diễn đànWiki.

Hôm nay mình sẽ giới thiệu với các bạn một số thuật toán liên quan đến kiểm tra nguyên tố của một số nguyên dương.

# Khởi đầu
Trong tập đề code cơ bản của bạn, kiểu gì cũng phải có bài kiểm tra nguyên tố.
Có một sự thật là khá nhiều bạn không biết phải làm thế nào với bài toán kiểm tra nguyên tố. Ta sẽ giải quyết bài toán này như thế nào?

# Thuật toán
## Một số tính chất nhỏ
- Nhắc lại về số nguyên tố: số nguyên tố là **số chỉ có 2 ước là 1 và chính nó**.
- Những số nào có nhiều hơn 2 ước là hợp số, tức là không phải số nguyên tố
- 0 và 1 không phải số nguyên tố và cũng không phải hợp số (hiển nhiên).
- Số nào cũng chia hết cho 1, cho nên kiểm tra tính chia hết với 1 là vô nghĩa.
- Số nào cũng chia hết cho chính nó, cho nên kiểm tra tính chia hết với chính nó cũng là vô nghĩa nốt.
Do vậy, khi ta nhắc đến 1 số `n` bất kì, ta đều biết nó đã có 2 ước dễ nhận thấy là 1 và chính nó. Khi ta kiểm tra nguyên tố, ta sẽ kiểm tra xem có số nào **khác 1 và chính nó** mà `n` chia hết hay không. Nếu nó chia hết cho 1 số nào đó (khác 1 và chính nó), ta kết luận nó không phải số nguyên tố.
Đến đây, bạn sẽ kêu "ôi, dễ ẹc, cho kiểm tra các số từ 2 đến n-1 là biết ngay ấy mà".
Việc kiểm tra từ 2 đến n-1 có vẻ ổn thoả, nhưng nó hơi thừa. Bạn có thấy rằng:
```
- Nếu n chia hết cho k thì n cũng chia hết cho (n/k) (hiển nhiên).

Với lại, số nguyên tố thứ 10001 nằm ngoài đoạn [2, 1000] rồi nhé.

Số nguyên tố không chỉ chia hết cho 2,3,5,7 (nắm nguyên tắc số nguyên tố mà làm)

Bạn nên viết riêng 1 method kiểm tra số nguyên tố(vd num):

• IsPrime:
  num <=1 không phải số nguyên tố
  num =2 là số nguyên tố
  xét các số từ 3 tới căn bậc 2 của num. Có thể dùng vòng lặp for hoặc while với bước nhảy +=2. Vì 2 là số nguyên tố chẵn duy nhất.
• Rồi tới tìm số nguyên tố thứ 10001 bằng for hay while tùy ý.

Ah sau khi tìm ra rồi thì đo xem tìm hết bao nhiêu thời gian với python nhé. Làm ProjectEuler quan trọng là tối ưu thuật toán sao cho thời gian chạy nhanh nhất.

Mình viết trên C# mất 12ms trên máy win10, core i3 gen 2, ram 4gb

Bạn thử lưu kết quả trước lại xem có nhanh hơn ko??

thuật toán kiểm tra số nguyên tố của bạn sai rồi nhé. Lúc trước Introduction programming with Python, mình cũng giải ProjectEuler bằng python. Tuy lâu nhưng vì mới nhập môn nên thấy cũng hay và có ích. Có bài tận 1 tiếng mới ra kết quả

Bài nào bạn

Mà bài này sàng rất nhanh.