แล้วก็มาถึงปริศนาข้อสุดท้ายซึ่งเป็นโจทย์วัดความรู้ด้านวิทยาศาสตร์คอมพิวเตอร์ คราวนี้เป็นเรื่องของ Prime Number หรือจำนวนเฉพาะ ซึ่งเป็นตัวเลขที่นักคณิตศาสตร์ศึกษากันมาอย่างยาวนานตั้งแต่ก่อนยุคคริสตกาลเสียอีก
จำนวนเฉพาะคือตัวเลขจำนวนเต็มบวกที่มากกว่า 1 โดยสามารถหารด้วยเฉพาะเลข 1 หรือตัวมันเองได้ลงตัวเท่านั้น ตัวอย่างเช่น เลข 5 ถือเป็นจำนวนเฉพาะ เพราะสามารถหารด้วย 1 และ 5 ลงตัว แต่เลข 6 ไม่ใช่จำนวนเฉพาะ เพราะนอกจาก 1 และ 6 แล้ว มันยังถูกหารด้วย 2 หรือ 3 ได้ลงตัวอีกด้วย ตัวอย่างของจำนวนเฉพาะ 30 ตัวแรกได้แก่ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109 และ113
โจทย์ของ Google Treasure Hunt ข้อสุดท้ายนี้ดูเข้าใจไม่ยาก แต่การหาคำตอบก็ไม่ง่ายนัก โดยให้หาเลขจำนวนเฉพาะที่น้อยที่สุดและมีค่าเท่ากับผลรวมของเลขจำนวนเฉพาะที่อยู่ติดกัน n ชุด โดยที่เลขในแต่ละชุดมีจำนวนไม่เท่ากัน ตัวอย่างเช่น ให้หาเลขจำนวนเฉพาะที่มีค่าน้อยที่สุดที่เท่ากับ
ผลรวมของจำนวนเฉพาะ 3 ตัวติดกัน
ผลรวมของจำนวนเฉพาะ 6 ตัวติดกัน
ซึ่งคำตอบของตัวอย่างนี้ก็คือ 41 เพราะจำนวนเฉพาะ 3 ตัวติดกันที่บวกแล้วได้ 41 ก็คือ 11 + 13 + 17 และจำนวนเฉพาะ 6 ตัวติดกันที่บวกแล้วได้ 41 ก็คือ 2 + 3 + 5 + 7 + 11 + 13
โจทย์ที่ผมได้รับให้หาจำนวนเฉพาะที่มีค่าน้อยที่สุดที่เท่ากับ
ผลรวมของจำนวนเฉพาะ 5 ตัวติดกัน
ผลรวมของจำนวนเฉพาะ 7 ตัวติดกัน
ผลรวมของจำนวนเฉพาะ 307 ตัวติดกัน
ผลรวมของจำนวนเฉพาะ 615 ตัวติดกัน
ผลรวมของจำนวนเฉพาะ 1211 ตัวติดกัน
จะเห็นได้ว่าโจทย์ข้อนี้ต้องเขียนวนลูปกันมหาศาลแน่นอน วนลูปแรกคือการหาชุดของเลขจำนวนเฉพาะที่อยู่ติดกัน อย่างน้อยก็ต้องหาเลขจำนวนเฉพาะ 1211 ตัวแรกให้ได้ วนลูปที่สองคือจะต้องทำการบวกเลขจำนวนเฉพาะที่อยู่ติดกันตามที่โจทย์กำหนด วนลูปที่สามก็คือต้องหาตัวเลขที่เป็นคำตอบที่เท่ากับผลรวมตามเงื่อนไขของโจทย์ให้ได้
สิ่งที่โจทย์ข้อนี้กำลังวัดก็คือคุณจะมีวิธีเขียนโปรแกรมที่ประหยัดเวลาในการประมวลผลของคอมพิวเตอร์ได้ดีแค่ไหน เพราะถ้าเขียนวนลูปแบบตรงไปตรงมา รับรองว่าใช้เวลาหลายชั่วโมงแน่นอน แต่ถ้าเขียนได้ดีจะใช้เวลาเพียงไม่กี่วินาที
นักคอมพิวเตอร์เรียกวิธีการออกแบบลอจิกในการเขียนโปรแกรมว่า Algorithm และเรียกวิธีการวัดประสิทธิภาพของ Algorithm ว่า Big O ตัวอย่างเช่น ถ้าคุณออกแบบ Algorithm ให้วนลูปตั้งแต่ 1 ถึง n โดยลูปนี้อยู่ภายใต้ลูปใหญ่ 1 ถึง n อีกชั้น แบบนี้ Big O จะมีค่า O(n2) ซึ่งถ้า Big O ของ Algorithm ที่เราออกแบบดันเป็นเลขยกกำลังแบบนี้ มันจะส่งผลต่อเวลาที่ใช้ในการประมวลผลเมื่อจำนวนข้อมูล (n) มีค่าสูงขึ้น เช่น ถ้า n=1,000 และ O(n2) แบบนี้คอมพิวเตอร์อาจจะต้องวนลูปถึง 1,000,000 รอบ แต่ถ้า O(nm) โดยที่ n=1,000 และ m=10 แบบนี้คงต้องนั่งรอกันเป็นชาติ
ปริศนาข้อสุดท้ายนี้จึงต้องหาวิธีออกแบบ Algorithm สำหรับแก้ปัญหาโดยที่มี Big O ต่ำๆ ด้วย และนี่คือวิธีคิดแบบของผมครับ
ผมเริ่มจากการวนลูปเพื่อหาชุดของจำนวนเฉพาะก่อน โดยที่ผมหาเผื่อไว้ประมาณสองแสนกว่าจำนวน (หาเยอะเกินไปหน่อย) ตั้งแต่ 2, 3, 5 ไปเรื่อยๆ จนถึง 2999999 นำตัวเลขที่หาได้ทั้งหมดบันทึกลงไฟล์ไว้ แล้วเขียนโปรแกรมอ่านข้อมูลจากไฟล์มาเก็บลงตัวแปร array อีกทีเพื่อให้ใช้งานได้สะดวก
ต่อมาก็ต้องเขียนโปรแกรมสำหรับวนลูปเพื่อบวกเลขจำนวนเฉพาะที่อยู่ติดกัน โดยผลบวกจะต้องมีค่าที่ตรงกับเงื่อนไขที่ต้องการ เช่น ผลบวกต้องเป็นจำนวนเฉพาะ หรือผลบวกจะต้องมีค่ามากกว่าหรือเท่ากับตัวเลขที่เรากำหนด จุดนี้ทำให้เกิดการวนลูปที่ค่อนข้างเยอะ เช่น ถ้าเราบวกเลขจำนวนเฉพาะตัวที่ 1 – 5 (2 + 3 + 5 + 7 + 11 = 28) แต่ผลลัพธ์ที่ได้ยังไม่ใช่จำนวนเฉพาะตามที่เราต้องการ เราก็ต้องเปลี่ยนไปวนลูปบวกเลขจำนวนเฉพาะตัวที่ 2 – 6 (3 + 5 + 7 + 11 + 13 = 39) ซึ่งก็ยังไม่ใช่จำนวนเฉพาะอีก ก็ต้องเปลี่ยนไปเป็นตัวที่ 3 – 7 แบบนี้ไปเรื่อยๆ จนกว่าจะพบคำตอบที่ต้องการ
แต่ถ้าต้องบวกเลข 1211 ตัวติดกัน และต้องวนหลายๆ ครั้งล่ะ มันจะช้าขนาดไหน?
ตรงจุดนี้พอจะมีทริคที่ช่วยให้วนลูปได้น้อยๆ อยู่ ก็คือแทนที่เราจะต้องวนลูปบวกทุกครั้ง ให้เปลี่ยนเป็นวนลูปบวกเฉพาะตัวเลขชุดแรก พอจะหาผลบวกของตัวเลขชุดที่สองก็ให้เอาผลบวกชุดแรกมาลบออกด้วยตัวเลขแรกของชุดแรก และบวกเพิ่มด้วยตัวเลขถัดจากตัวเลขสุดท้าย
ด้วยวิธีนี้ จากลูปซ้อนลูปก็จะเหลือเพียงแค่ลูปชั้นเดียว Big O ลดลงทันทีอย่างมีนัยสำคัญ
เมื่อใช้ Algorithm นี้เพื่อหาผลรวมของเลขจำนวนเฉพาะที่อยู่ติดกัน 1211 ตัวได้แล้ว ก็จะต้องนำผลรวมที่ได้มาทดสอบกับเงื่อนไขอื่นอีก 4 เงื่อนไข คือผลรวมของ 1211 ตัวติดกันจะต้องเท่ากับผลรวมของ 615, 307, 7 และ 5 ตัวติดกันด้วย วิธีการหาผลรวมของอีก 4 เงื่อนไขก็ทำได้คล้ายๆ กัน เพียงแต่มีเงื่อนไขเพิ่มขึ้นจากเดิมที่จะวนลูปจนกว่าจะได้คำตอบที่เป็นจำนวนเฉพาะ คราวนี้จะเปลี่ยนเป็นวนลูปจนกว่าจะได้คำตอบมากกว่าหรือเท่ากับผลรวมของ 1211 ตัวติดกัน ถ้าทั้ง 4 เงื่อนไขให้คำตอบเดียวกันกับผลรวมของ 1211 ตัวติดกัน แสดงว่านั่นคือคำตอบ แต่ถ้าเงื่อนไขใดให้คำตอบที่มากกว่า ก็จะต้องวนกลับไปหาผลรวมของ 1211 ตัวติดกันอีกรอบ โดยขยับไปที่ตัวเลขจำนวนเฉพาะตัวถัดไป
จาก Flowchart จะเห็นว่ายังมีจุดที่สามารถลด Big O ลงได้อีก นั่นก็คือตรง i2 = 1 ซึ่งมันไม่จำเป็นจะต้องเป็น 1 แต่ควรจะเป็นตัวเลขที่มากกว่านี้ การกำหนดให้เป็น 1 ทำให้ต้องวนลูปมากขึ้น ตัวอย่างเช่น ถ้าโจทย์ให้หาคำตอบของเลข 3 และ 6 ตัวติดกัน เราจะเริ่มหาจำนวนเฉพาะที่เกิดจากผลรวมของเลข 6 ตัวติดกันก่อน นั่นก็คือ 2 + 3 + 5 + 7 + 11 + 13 = 41 จากนั้นจึงหาผลรวมของเลข 3 ตัวติดกัน ในกรณีที่ i2 = 1 นั่นแปลว่าเราเริ่มตั้งแต่ 2 + 3 + 5 = 10 แล้วค่อยเลื่อนไปเป็น 3 + 5 + 7 = 15 และ 5 + 7 + 11 = 23 ซึ่งจะเห็นได้ว่าคำตอบในชุดเลขช่วงแรกจะไม่มีทางเท่ากับ 41 ได้เลย เพราะตัวเลขยังน้อยอยู่ กว่าจะเท่ากับ 41 ได้ก็เมื่อ 11 + 13 + 17 = 41 การกำหนดให้ i2 = 1 จึงเป็นการสิ้นเปลือง
แล้วเราควรจะให้ i2 เป็นเท่าไหร่ดีล่ะ? วิธีการที่ผมใช้คือนำจำนวนเลขติดกันจากเงื่อนไขก่อนหน้า (6) มาลบด้วยจำนวนเลขติดกันของเงื่อนไขปัจจุบัน (3) และบวกด้วยตำแหน่งเริ่มต้นของเลขจำนวนเฉพาะที่ใช้หาผลบวก (1) ในกรณีนี้ได้คำตอบคือ i2 = 6 – 3 + 1 = 4 ดังนั้นจะเริ่มบวกตั้งแต่ 7 + 11 + 13 เป็นต้นไป ทำให้ไม่ต้องเสียเวลาวนลูปบวกเลข 3 ชุดแรกเลย ตัวอย่างนี้อาจจะดูเหมือนน้อย แต่ถ้าเปลี่ยนสมการเป็น i2 = 1211 – 615 + i1 จะเห็นได้ว่าสามารถลดการวนลูปไปได้ถึงหลายร้อยรอบ ซึ่งถ้าในแต่ละรอบมีลูปซ้อนยุ่งเหยิงอยู่ข้างในก็จะยิ่งช่วยประหยัดเวลาประมวลผลได้อีกมาก
จากโจทย์และ Algorithm นี้ ผลงานที่ผมทำได้โดยใช้ PHP, Windows XP และโน้ตบุ๊กธรรมดาๆ ใช้เวลาหาคำตอบไม่ถึง 1 วินาที (ไม่นับรวมการวนลูปเพื่อเตรียมเลขจำนวนเฉพาะลงไฟล์ในตอนแรก) คำตอบที่ได้ก็คือ
ผลรวมของจำนวนเฉพาะ 1211 ตัวติดกัน = ผลรวมของจำนวนเฉพาะตัวที่ 73 (367) + ตัวที่ 74 (373) + … + ตัวที่ 1283 (10487) = 6277987
ผลรวมของจำนวนเฉพาะ 615 ตัวติดกัน = ผลรวมของจำนวนเฉพาะตัวที่ 941 (7417) + ตัวที่ 942 (7433) + … + ตัวที่ 1555 (13049) = 6277987
ผลรวมของจำนวนเฉพาะ 307 ตัวติดกัน = ผลรวมของจำนวนเฉพาะตัวที่ 2154 (18919) + ตัวที่ 2155 (18947) + … + ตัวที่ 2460 (21943) = 6277987
ผลรวมของจำนวนเฉพาะ 7 ตัวติดกัน = ผลรวมของจำนวนเฉพาะตัวที่ 71051 (896783) + ตัวที่ 71052 (896803) + … + ตัวที่ 71057 (896921) = 6277987
ผลรวมของจำนวนเฉพาะ 5 ตัวติดกัน = ผลรวมของจำนวนเฉพาะตัวที่ 96860 (1255567) + ตัวที่ 96861 (1255591) + … + ตัวที่ 96864 (1255619) = 6277987
ใครที่เล่น Google Treasure Hunt และสามารถหาคำตอบได้ด้วยตัวเองทั้ง 4 ข้อ คุณเรียกตัวเองว่า Geek ได้เลยครับ!