{ first 10-digit prime found in consecutive digits of e } .com** คำเตือน : บล็อคตอนนี้เป็นเรื่องวิชาการล้วนๆ
– ต่อจากตอนที่แล้ว –
ผมนั่งงงกับโจทย์นี้อยู่หลายรอบ .. คำถามสำคัญก็คือ “มันแปลว่าอะไรวะ !!??”
หลังจากเปิด dict ดูอีกรอบสองรอบ ก็เลยถึงบางอ้อว่า .. จริงๆแล้วถ้าแปลโจทย์นี้เป็นภาษาไทยก็คือ ..
“{ จำนวนเฉพาะ 10 ตัวแรกที่พบในค่า e } .com”
ถ้า มันทำให้ยิ่งงง นั่นก็ไม่ใช่เรื่องแปลก แต่ถ้าอ่านดูดีๆ แล้วจะรู้ได้เลยว่ามันก็ไม่มีอะไรมาก .. ก่อนอื่นเราต้องรู้จักค่า e ก่อน จริงๆแล้ว e เป็นค่าคงที่ทางคณิตศาสตร์ ที่เราทุกคนเคยเรียนมาแล้วตอนม.ปลาย แต่เชื่อได้ว่าส่วนใหญ่ลืมกันไปหมดแล้ว
e คือค่าคงที่ หรือที่เรียกกันว่า exponential ใช้กันมากในการคำนวณในวิชาฟิสิกส์ … คล้ายๆกับค่าพาย π ที่มีค่าเท่ากับ 22 / 7
แล้ว e มีค่าเท่ากับเท่าไหร่ ? หาค่านี้ยังไง ?
อันนี้จำไม่ได้จริงๆ ก็ต้องพึ่ง wikipedia ล่ะครับ (วิธีทำการบ้านยุค 2.0) ก็ได้ความว่า ค่า e หาได้จากสมการที่ไม่ซับซ้อนอะไรมากประมาณนี้ :
ก็จะได้ว่า e มีค่าประมาณ 2.7182818284 59045 23536 …. ยาวออกไปเรื่อยๆ ไม่มีวันจบ คล้ายๆกับค่าพายเหมือนกัน
กลับ มาที่โจทย์อีกครั้ง .. “จำนวนเฉพาะ 10 ตัวแรกที่พบในค่า e” .. ขยายความได้ว่า ให้เอาเลขทศนิยมของเจ้าค่า e เนี่ย ออกมาดูทีละ 10 ตัว แล้วดูว่ามันใช่จำนวนเฉพาะรึเปล่า ถ้าไม่ใช่ก็ให้ดูตัวต่อไปเรื่อยๆ จนกว่าจะเจอ .. ตัวแรกที่เจอ ให้เอาค่านั้น ตามด้วย .com ก็จะเจอเว็บปริศนา
วาดเป็นรูปออกมาให้เข้าใจง่ายๆ ประมาณนี้ :
จะเห็นว่าถ้าไม่มาเขียนโปรแกรมเพื่อหาคำตอบคงไม่มีทางหาค่านี้ได้เลย ว่าแล้วก็เปิด eclipse ลงมือเขียนทันที
1. เริ่มแรกคือต้องหาค่า e ก่อน .. จริงๆ java มีค่า e มาให้อยู่แล้วที่ Math.E เพียงแต่ว่ามันดันมีทศนิยมมาให้แค่ 19 หลัก ซึ่งไม่น่าจะพอ เพราะเราก็ไม่รู้ว่าจะต้อง shift right ไำปหาทศนิยมจนถึงหลักที่เท่าไหร่กันแน่ เพราะงั้นก็ต้องเขียน function ขึ้นมาหาค่า e โดยเฉพาะ
2. จากสูตรข้างบน จะเห็นว่าเราจะต้องมี function ช่วยอีกตัวนึง คือหาค่า factorial โดยเขียนเป็น recursive เพื่อให้ได้ผลคูรออกมา เช่น ถ้าให้หา 3! ก็จะต้องได้ค่า 6 กลับมา ( 3! = 3 x 2 x 1 = 6 )
ก็ได้ออกมาประมาณนี้
สาเหตุที่ต้องใช้ BigDecimal เพราะลองใช้ double แล้วไม่เวิร์ค มันจะได้ค่า infinity ออกมา ถ้าเราลองทำซัก 1,000 ตัว
3. หาค่า e โดยการวนลูป แล้วบวกค่าไปเรื่อยๆ ในรูปนี้คือทำทั้งหมด 1,000 รอบ และใช้วิธีการหารให้ได้ทศนิยม 1,000 ตำแหน่ง
4. เสร็จแล้วก็ทดสอบดูว่าได้ค่า e ออกมาเหมือนชาวบ้านชาวเมืองเค้ารึเปล่า จากนั้นก็เขียน function ทดสอบว่าค่านี้เป็นจำนวนเฉพาะรึเปล่า (จำนวนเฉพาะคือเชขที่ไม่มีเลขใดๆ หารมันลงตัว ยกเว้น 1 กับตัวมันเอง เช่น 2 , 3 , 5 , 7 , 11 , 13 )
ที แรกใช้วิธีไล่หารมันทีละตัวเลย เริ่มตั้งแต่ 2 ไปจนถึงจำนวนของมันเอง ซึ่งก็พอจะใช้งานได้ แต่พอเจอกับตัวเลขมากๆ ถึง 10 หลักเนี่ย ก็รอเป็นชาติเลยกว่าจะได้ผลลัพท์ออกมา เพราะมันต้องวนลูปทั้งหมด n ครั้ง คือ O(n) อย่างดีที่สุดคือวนครั้งเดียว แต่อย่างแย่ก็คือต้องวน 999,999,999 ครั้ง
ก็เลยต้องพยายามให้ Big O ลดลงมาให้ได้มากที่สุด จริงๆปัญหาจำนวนเฉพาะนี้เคยเจอมาหลายรอบตอนแข่ง Google Code Jam ก็พอจะมีเทคนิคอยู่บ้าง
อย่างแรกคือ ถ้าตัวเลขเป็นเลขคู่ มันไม่ใช่จำนวนเฉพาะแน่นอน เช่น ลงท้ายด้วย 2 , 4 , 6 , 8
สองคือการหาตัวเลขมากที่สุดที่จะเอามาหาร ถ้าสังเหตุดีๆ เลขที่ไม่ใช่จำนวนเฉพาะ เช่น
6 = 3 x 2
21 = 7 x 3
121 = 11 x 11
231 = 11 x 7 x 3
ตัว เลขในกลุ่มที่หารมันได้ลงตัว จะมีค่าไม่เกิน square root ของตัวมันเอง .. เช่น sqr ( 231 ) = 15.19 ดังนั้นเราตั้งหารไปเรื่อยๆ จนถึงแค่เลข 15 ก็พอแล้ว
เท่านี้ก็ลด Big O ไปได้หลายเท่าตัว แล้วก็ได้ function หาจำนวนเฉพาะประมาณนี้
5. สุดท้ายก็เขียนตัวทำงานหลัก ก็ไม่มีอะไรมาก เริ่มจากหาค่า e จากนั้นก็ดึงตัวเลขหลังทศนิยมออกมาทีละ 10 ตัว มาเช็คว่าเป็นจำนวนเฉพาะรึเปล่า ถ้าไม่ใช่ก็ให้เลื่อนไปอีกหนึ่งตัวหาค่าต่อไป
สั่งทำลานโลด ว่าแล้วก็ได้ออกมาแล้ว … { first 10-digit prime found in consecutive digits of e } มันก็คือ …
7427466391 !!!
เขียนไปค่อนวัน กว่าจะได้เลขนี้ออกมา ว่าแล้วก็เปิดเข้าไปดูที่ 7427466391.com มันมี !! แล้วปรากฏว่า ..
อ๊ากก ก .. จะบ้าตาย .. มันหาเว็บไม่เจอ .. เอ๊ะ รึว่าเราคำนวณผิด ? ลองกลับไปดูใหม่อีกรอบ มันก็น่าจะถูกแล้ว ว่าแล้วก็เลยลอง search google ด้วยคำๆ นี้ โอ้ .. ทางกูเกิลบอกว่าปิดเว็บนี้ไปนานแล้ว เวรกรรม T__T
แต่ ก็แอบดีใจที่ได้คำตอบตรง พึ่งรู้เหมือนกันว่ามีคนทำโจทย์ข้อนี้ไปเยอะมาก ท่าจะข่าวดังจริงๆ ว่าแล้วก็ save เก็บโปรแกรมเล็กๆนี้ไว้ดูต่างหน้า ว่าอย่างน้อยก็ได้ลองทดสอบแก้ปัญหาสนุกๆ ข้อนึงได้
ปิดไฟ นอน .. หลับฝันดีอีกคืน
