โจทย์
จำนวนเฉพาะแฝด (twin primes) คือจำนวนเฉพาะสองจำนวนที่ต่างกันอยู่ 2 เช่น 11 กับ 13 หรือ 17 กับ 19 ให้หาทุกคู่ที่จำนวนตัวที่มากกว่ามีค่าไม่เกิน limit
จงเขียน twin_primes(limit)
ถ้า limit มีค่ามาก ให้หาจำนวนเฉพาะทั้งหมดพร้อมกันด้วยตะแกรง แทนการตรวจทีละจำนวน
อินพุต
limit: ค่าที่มากที่สุดที่จำนวนเฉพาะตัวที่มากกว่าในคู่จะมีได้
เอาต์พุต
คืนค่าลิสต์ของคู่ [p, p + 2] ที่ทั้งสองจำนวนเป็นจำนวนเฉพาะและ p + 2 ≤ limit เรียงตาม p จากน้อยไปมาก ถ้าไม่มีคู่เลยให้คืนค่าลิสต์ว่าง
เงื่อนไข
0 ≤ limit ≤ 10^6
ตัวอย่าง
อินพุต:
limit = 20
ผลลัพธ์ที่คาดหวัง:
expected = [
[3, 5],
[5, 7],
[11, 13],
[17, 19]
]
อินพุต:
long long limit = 20;
ผลลัพธ์ที่คาดหวัง:
std::vector<std::vector<long long>> expected = {
{3, 5},
{5, 7},
{11, 13},
{17, 19}
};
อินพุต:
long limit = 20;
ผลลัพธ์ที่คาดหวัง:
long[][] expected = new long[][] {
new long[] {3, 5},
new long[] {5, 7},
new long[] {11, 13},
new long[] {17, 19}
};
คำอธิบาย
จำนวนเฉพาะที่ไม่เกิน 20 คือ 2, 3, 5, 7, 11, 13, 17, 19 คู่ที่ห่างกัน 2 คือ [[3, 5], [5, 7], [11, 13], [17, 19]]
อินพุต:
limit = 6
ผลลัพธ์ที่คาดหวัง:
expected = [
[3, 5]
]
อินพุต:
long long limit = 6;
ผลลัพธ์ที่คาดหวัง:
std::vector<std::vector<long long>> expected = {
{3, 5}
};
อินพุต:
long limit = 6;
ผลลัพธ์ที่คาดหวัง:
long[][] expected = new long[][] {
new long[] {3, 5}
};
คำอธิบาย
3 และ 5 เป็นจำนวนเฉพาะทั้งคู่และ 5 ≤ 6 แต่ 7 เกินขีดจำกัด จึงได้แค่ [[3, 5]]
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
ตะแกรงหาจำนวนเฉพาะทั้งหมดจนถึง 10^6 ได้เร็วกว่าการตรวจทีละจำนวนมาก
คำใบ้ 2
จากนั้นตรวจ p ทุกตัวที่ p + 2 ≤ limit
คำใบ้ 3
คู่แรกคือ (3, 5) ดังนั้นถ้า limit น้อยกว่า 5 จะได้ลิสต์ว่าง
ความซับซ้อนที่คาดหวัง
เวลา O(limit log log limit), หน่วยความจำเพิ่ม O(limit)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน