|
สมัครสมาชิก | คู่มือการใช้ | รายชื่อสมาชิก | ปฏิทิน | ข้อความวันนี้ | ค้นหา |
|
เครื่องมือของหัวข้อ | ค้นหาในหัวข้อนี้ |
#1
|
|||
|
|||
พวกโจทย์ที่ถามว่า จำนวนเฉพาะ 1- 10000 นี่หายังไงครับ แบบรวดเร็ว
วันนั้นมีคนถามอะ งงเลย หาแบบเร็วๆนี่หายังไงครับ ช่วยชี้แจงด้วย
|
#2
|
||||
|
||||
เร็วสุดก็เปิดตารางน่ะครับ. ยิ่งจำนวนมีค่ามากยิ่งตรวจสอบยากมากขึ้นไปเรื่อย ๆ ว่าเป็นจำนวนเฉพาะหรือเปล่า ยังไม่มีทฤษฎีที่ใช้ตรวจสอบว่าจำนวนดังกล่าวเป็นจำนวนเฉพาะได้อย่างรวดเร็ว จะมีก็วิธีการตรวจสอบในเบื้องต้น โดยใช้ทฤษฎีในเรื่อง ทฤษฎีจำนวน (สำหรับจำนวนใหญ่ ๆ นะครับ.) เช่น ทบ.เล็กของแฟร์มาต์ (Fermat's little Theorem) ซึ่งก็จะใช้คอมพิวเตอร์คำนวณกัน
สำหรับวิธีการตรวจสอบที่ใช้ได้ผล 100% แต่ถ้าคิดด้วยมือก็เหนื่อยขึ้นตามความใหญ่ของจำนวน คือ ให้นำจำนวนเฉพาะที่น้อยกว่าหรือเท่ากับ รากที่สองที่เป็นบวกของจำนวนนั้น มาลองหารจำนวนดังกล่าวดู ถ้าไม่มีจำนวนใดที่หารลงตัว จึงสรุปได้ว่าเป็นจำนวนเฉพาะ เช่น 29 เป็นจำนวนเฉพาะหรือไม่ ? ึ29 ป 5.กว่า ๆ จำนวนเฉพาะที่น้อยกว่าหรือเท่ากับ 5.กว่า ๆ มี 2,3,5 เมื่อนำไปหาร 29 ดูจะพบว่าหารไม่ลงตัวเลย จึงสรุปว่า 29 เป็นจำนวนเฉพาะครับ. จะเห็นได้ว่าวิธีนี้ไม่ดีมากเท่าไรนัก ถ้าเอาจำนวนใหญ่ ๆ เช่น 8897 มาคิด เพราะเราต้องรู้ว่าจำนวนเฉพาะก่อนหน้า ึ8897 ป 94.กว่า นั้นมีอะไรบ้าง ซึ่งเป็นงานที่เหนื่อย ถึงแม้ว่าจะจำได้แม่นก็ตามเถอะว่าจำนวนเฉพาะที่ไม่เกิน 100 มีอะไรบ้าง
__________________
The Lost Emic <<-- หนังสือเฉลยข้อสอบระดับประถมนานาชาติ EMIC ครั้งที่ 1 - ครั้งที่ 8 ชุดสุดท้าย หลงมา 08 มกราคม 2005 21:20 : ข้อความนี้ถูกแก้ไขแล้ว 2 ครั้ง, ครั้งล่าสุดโดยคุณ gon |
#3
|
|||
|
|||
ใช้ computer serch ครับ
__________________
[[:://R-Tummykung de Lamar\\::]] || (a,b,c > 0,a+b+c=3) $$\sqrt a+\sqrt b+\sqrt c\geq ab+ac+bc$$ |
#4
|
||||
|
||||
ถ้าเป็นคำถามจากพวกทีั่เขียนโปรแกรม ก็น่าจะหมายถึงการทำให้โปรแกรมทำงานเร็วขึ้นมากกว่าครับ
เนื่องจากการทดสอบว่าจำนวนใด เป็นจำนวนเฉพาะ ปกติจะทำโดยการไล่นำเลขตั้งแต่ 2 จนถึง จำนวนนั้น-1 ไปหารทดสอบ ถ้ามีการหารลงตัวเกิดขึ้น จำนวนนั้นก็ไม่เป็นจำนวนเฉพาะ แต่ในทางปฎิบัติจริงๆแล้ว ไม่จำเป็นต้องไล่หารไปซะทุกตัวครับ หารถึงแค่รากที่สองของจำนวนที่จะทดสอบก็ได้แล้ว เพราะ จำนวนเต็มบวก n จะไม่เป็นจำนวนเฉพาะ ก็ต่อเมื่อ มีตัวไปหารแล้วลงตัวอย่างน้อยหนึ่งตัว สมมติว่าแยกได้เป็น a x b พบว่า ถ้ามีตัวประกอบที่มากกว่า sqrt(n) เป็นตัวประกอบ ก็จะมีตัวประกอบที่น้อยกว่า sqrt(n) ด้วย ( ก็จะเกิดการหารลงตัวขึ้น ) ดังนั้นเราจึงไม่จำเป็นต้องหารไปจนครบครับ ยิ่ง n มากๆ ก็จะยิ่งเห็นได้ชัด นี่เป็นวิธีเบื้องต้นในการตรวจจำนวนเฉพาะครับ คิดว่าคำตอบที่คนถามต้องการน่าจะหมายถึงแบบนี้มากกว่า
__________________
Mmmm .... |
#5
|
||||
|
||||
อืมมม ถ้าเป็นแนวคอมพิวเตอร์ จะถาม 1 ถึง 1000000 ด้วยซ้ำนะคับ
มี เทคนิคทาง algorithm หลายรูปแบบที่ใช้ จำได้ว่าชื่อ dynamic programming หรืออย่างไรเนี่ยแหละคับ ถ้าสนใจพวกนี้ศึกษาในวิชา algorithm ได้คับ
__________________
PaTa PatA pAtA Pon! |
#6
|
|||
|
|||
พูดถึง 2-10,000 นี่ไม่ใช้คอมพ์ก็หนักไปนะ แต่ใช้คอมพ์ก็ง่ายไปอีก ในกรณีที่ใช้คอมพ์
ผมว่าวิธีที่ดีที่สุดก็คือการใช้ Sieve of Eratosthenes นะครับ ซึ่งคิดว่าทุกคนคงเคย เห็นกันมาแล้ว โดยวิธีนี้เราจะไม่ต้องใช้การหารเลย (ในการกระทำพื้นฐาน 4 อย่างคือ บวก ลบ คูณ หารนั้น หารจะเป็นอันที่ช้าที่สุด) |
#7
|
|||
|
|||
ใช้ mathematica ครับ 555
|
|
|