Tại sao kiểm tra số nguyên tố phải kiểm tra đến căn bậc 2 của number?

ai có thể giúp em trả lời là tại sao kiểm tra số nguyên tố lại phải kiểm tra đến căn bậc 2 của number không

em có giải thích theo mấy cách trên mạng mà thầy không nghe

merged to the #1 post by noname00

vì nếu i chạy quá căn n thì nếu n chia hết cho i, j = n/i là số nguyên, và j sẽ bé hơn căn n, nghĩa là j đã được duyệt trước đó rồi (i chạy từ 2 tới căn n trước đó). Còn nếu trước đó từ 2 tới căn n ko có i nào n chia hết nghĩa là ko thể tồn tại số nguyên j = n/i với i > căn n

10 Likes

Số bé * số lớn ra n (lấy ví dụ n = 12, 12 = 2 * 6 = 3 * 4 :smiley: )
Hai số vượt quá sqrt thì tích lớn hơn cả n rồi, vậy nếu có thì chỉ cần tìm trong (1, \sqrt{n}\ ].

17 Likes

nếu n không phải nguyên tố thì có thể phân tích dưới dạng tích 2 ước số a, bn = a * b

và hiển nhiên ab không thể cùng lớn hơn \sqrt{n}, vì nếu lớn hơn thì chúng ta sẽ có tích a * b > \sqrt{n} * \sqrt{n} = n

vậy nên trong các ước số của n, thì ít nhất 1 trong các ước sẽ nhỏ hơn \sqrt{n} và nếu chúng ta không thể tìm được ước số nào thuộc [2, \sqrt{n}] thì suy ra n là nguyên tố

hoặc là …
i^2 \leq n => i \leq \pm \sqrt{n} :penguin:

9 Likes

Với n \in \Z^+ \setminus \{1\} nếu n là hợp số thì \exists\ a, b \in \Z^+\setminus\{1\}, n = ab (định nghĩa)

Giả thiết a, b > \sqrt{n} \implies ab > \sqrt{n}\sqrt{n} = n mâu thuẫn với dòng trên, vậy ta có thể kiểm tra hợp số bằng cách chia thử tới \sqrt{n}.


Định nghĩa số nguyên tố có thể phát biểu là: (Với n\in Z^+ \setminus \{1\})

\nexists\ a, b \in \Z^+ \setminus\{1\}, n = ab

(vì ta ngầm hiểu 1 là khác “chính nó”).

Dễ thấy hai mệnh đề là phủ định của nhau, hay không phải hợp số thì là số nguyên tố.

11 Likes

học lại lớp 6 để hiểu hơn về số nguyên tố
học lại lớp 9 để hiểu hơn về lý do vì sao check đến căn bậc 2

7 Likes

Liệu có ai sẽ tìm ra một số nào khác có “chi phí” còn thấp hơn cả “check đến căn bậc 2” hay không?

6 Likes

Chỉ cần căn bậc 2 là đảo của bình phương thôi :smiley: (đang xét số dương)


https://primes.utm.edu/prove/index.html

5 Likes

Cám ơn tất cả mọi người,mình đã tìm được câu trả lời,trong toán học vì n=sqrt(n) * sqrt(n),nên
nếu đoạn từ [1- sqrt(n)] có 1 ước chung thì đoạn [sqrt(n)-n] cũng chỉ có thể có 1 ước,vì [1- sqrt(n)]=[sqrt(n)-n],vì thế chỉ cần xét đoạn từ [1- sqrt(n)],Chỉ khi mình giải thích thế thì thầy mình mới chấp nhận còn những câu trả lời khác câu này thì thầy đều say No

4 Likes

Vậy ý bạn là mỗi ước d \in (1, \sqrt{n}\ ] tương ứng với đúng một ước d' \in [\sqrt{n}, n) của n.

7 Likes

là sao t vẫn không hiểu ông nói gì. Ví dụ như sqrt(100) = 10. Thì đoạn [1 - 10] đâu có bằng
[10 - 100].

Về mặt toán học, nếu i là một ước của n thì n / i cũng là một ước của n. Nếu i \le \sqrt{n} thì tất nhiên n/i \ge \sqrt{n}.

Do vậy, để tránh kiểm tra trùng cặp ước (i, n/i), ta chỉ cần kiểm tra đến \sqrt{n} là đủ.

Ví dụ n = 100, bạn đã gặp ngay 1 ước i = 2 thì bạn chẳng cần kiểm tra ước j = 50 làm gì cả. Bạn gặp 1 ước i \ne 1 thì việc kiểm tra kết thúc ngay lập tức mà không cần kiểm tra thêm ước n / i làm gì cả.

8 Likes

Ý là số ước trong đoạn [1, 10] bằng số ước trong đoạn [10, 100].

Xét d \mapsto \frac{n}{d}, d \leq \sqrt n, d \mid n. Như vậy miền giá trị là d' \geq \sqrt n, d' \mid n.

  • \frac{n}{d_1} = \frac{n}{d_2} \Rightarrow d_1 = d_2
  • \forall d \mid n, n / (n / d) = n \cdot d / n = d

Vậy hàm trên là song ánh \square

4 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?