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

Le_Duy1 · July 9, 2018, 10:32am

em dùng python dể làm projecteuler, em tới vòng 7 rồi, đề bài là tìm số nguyên tố thứ 10 001(10 ngàn lẻ 1), mọi người xem giúp em sai cái gì mà khi chạy nó ra 53 54 55 56 57 58

#problem7
count=1
n=1000
while count < 10002:
    for i in range (2,n+1):
        if (i%2!=0)and(i%3!=0)and(i%5!=0)and(i%7!=0)and(i%8!=0)and(i%9!=0):
            count+=1
        if count == 10001:
            print(i)

noname00 · July 9, 2018, 9:23am

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é:

github.com

neihousaigaai/DNHWiki/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 DNHWiki.

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).

This file has been truncated. show original

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

nguyenthanhdanh55162 · July 9, 2018, 11:13am

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)

binbo0102 · July 9, 2018, 5:26pm

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

HoangNew · July 9, 2018, 5:27pm

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

Xuan_Ngoc · July 10, 2018, 3:30am

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ả

rogp10 · July 10, 2018, 3:43am

Bài nào bạn

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