โจทย์ทั้งหมด
ง่าย 0 ข้อที่แก้แล้ว อัตราผ่าน 0%

จำนวนเฉพาะแฝด

หาจำนวนเฉพาะแฝด (p, p + 2) ทุกคู่ที่ไม่เกินขีดจำกัดที่กำหนด

สิ่งที่คุณจะได้เรียนรู้

  • ทำเครื่องหมายจำนวนเฉพาะจนถึงขีดจำกัดด้วยตะแกรง
  • ไล่หาจำนวนเฉพาะที่ห่างกัน 2
  • จัดการขีดจำกัดที่เล็กเกินกว่าจะมีคู่ใดเลย

โจทย์

จำนวนเฉพาะแฝด (twin primes) คือจำนวนเฉพาะสองจำนวนที่ต่างกันอยู่ 2 เช่น 11 กับ 13 หรือ 17 กับ 19 ให้หาทุกคู่ที่จำนวนตัวที่มากกว่ามีค่าไม่เกิน limit

จงเขียน twin_primes(limit)

ถ้า limit มีค่ามาก ให้หาจำนวนเฉพาะทั้งหมดพร้อมกันด้วยตะแกรง แทนการตรวจทีละจำนวน

อินพุต

limit: ค่าที่มากที่สุดที่จำนวนเฉพาะตัวที่มากกว่าในคู่จะมีได้

เอาต์พุต

คืนค่าลิสต์ของคู่ [p, p + 2] ที่ทั้งสองจำนวนเป็นจำนวนเฉพาะและ p + 2 ≤ limit เรียงตาม p จากน้อยไปมาก ถ้าไม่มีคู่เลยให้คืนค่าลิสต์ว่าง

เงื่อนไข

0 ≤ limit ≤ 10^6

ตัวอย่าง

ตัวอย่างที่ 1
อินพุต:
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]]

ตัวอย่างที่ 2
อินพุต:
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 กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน

คำตอบที่ผ่านดีที่สุดของแต่ละคน คำตอบที่เร็วกว่า ใช้หน่วยความจำน้อยกว่า และได้คะแนนดีกว่าจะอยู่ด้านบน

ยังไม่มีคำตอบที่ผ่าน แก้โจทย์นี้แล้วคว้าอันดับหนึ่งไปเลย

เรียนรู้จากคนอื่น

แนวทางจากชุมชน

ยังไม่มีวิธีทำที่เผยแพร่ ลองแก้โจทย์นี้เพื่อแชร์วิธีแรก