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
Tại sao kiểm tra số nguyên tố phải kiểm tra đến căn bậc 2 của number?
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 
)
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}\ ].
18 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, b là n = a * b
và hiển nhiên a và b 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} 
11 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 (đang xét số dương)
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?