คำตอบของทีม
ไม่ได้ส่งคำตอบ
ไม่ได้ส่งคำตอบ
คะแนน + โบนัสทำเร็ว
0.0
0.0
แชร์
ไม่ได้ส่งคำตอบ 
พิจารณาขั้นตอนวิธีต่อไปนี้ ที่ทำงานกับอาร์เรย์ A ขนาด 100,000 ช่อง (ข้อมูลในอาร์เรย์เก็บตั้งแต่ A[0] ถึง A[99999])
1. for x = 0 to 99999 do: A[x] $\leftarrow$ 0; endfor
2. for x = 2 to 99999 do
3. $\quad$ if A[x] = 0 then
4. $\quad \quad$ y $\leftarrow$ x + x
5. $\quad \quad$ while y <= 99999 do: A[y] $\leftarrow$ A[y] + 1; y $\leftarrow$ y + x; endwhile
6. $\quad$ endif
7. endfor
ค่าดัชนี x ของอาร์เรย์ A ใดที่มีค่า A[x] มากที่สุด ถ้ามีดัชนีที่ให้คำตอบมากที่สุดหลายค่า ให้ตอบคำตอบที่น้อยที่สุด
1. for x = 0 to 99999 do: A[x] $\leftarrow$ 0; endfor
2. for x = 2 to 99999 do
3. $\quad$ if A[x] = 0 then
4. $\quad \quad$ y $\leftarrow$ x + x
5. $\quad \quad$ while y <= 99999 do: A[y] $\leftarrow$ A[y] + 1; y $\leftarrow$ y + x; endwhile
6. $\quad$ endif
7. endfor
ค่าดัชนี x ของอาร์เรย์ A ใดที่มีค่า A[x] มากที่สุด ถ้ามีดัชนีที่ให้คำตอบมากที่สุดหลายค่า ให้ตอบคำตอบที่น้อยที่สุด
1)
10000
2)
30030
3)
65536
4)
99330
เฉลย
ตอบ 2) 30030
แนวคิด
สามารถหาคำตอบโดยการเขียนโปรแกรมหาคำตอบ หรือจะใช้การวิเคราะห์ทางคณิตศาสตร์ก็ได้
โปรแกรมด้านบนนับจำนวนตัวประกอบที่เป็นจำนวนเฉพาะที่ไม่ซ้ำกันของค่า x เก็บไว้ในอาร์เรย์ A[x] ดังนั้นจำนวนที่มีค่าในอาร์เรย์สูง จะเป็นจำนวนที่มีตัวประกอบเป็นจำนวนเฉพาะแตกต่างกันหลายตัว เราสามารถทดลองแทนค่าจำนวนที่มีตัวประกอบเฉพาะโดยไล่จากจำนวนเฉพาะที่มีค่าน้อยได้ดังนี้
2x3x5x7 = 210
2x3x5x7x11 = 2310
2x3x5x7x11x13 = 30030
2x3x5x7x11x13x17 = 510510 ซึ่งเกินขอบเขต
คำตอบจึงเป็น 30030
จำนวนอื่น ๆ ที่มีจำนวนตัวประกอบเฉพาะแตกต่างกัน 6 ตัว เช่น 46410 หรือ 99330 (แต่ไม่ตอบ 99330 เพราะโจทย์ถามดัชนีที่น้อยที่สุด)
โปรแกรมข้างต้นดัดแปลงจากขั้นตอนวิธี Sieve of Erastosthenes สำหรับหาจำนวนเฉพาะ