คำตอบของทีม
ไม่ได้ส่งคำตอบ
คะแนน + โบนัสทำเร็ว
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) 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 สำหรับหาจำนวนเฉพาะ