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

นับจำนวนเฉพาะในช่วงที่กำหนด

นับว่ามีจำนวนเฉพาะกี่ตัวที่อยู่ระหว่างขอบเขตทั้งสอง โดยรวมค่าที่ขอบด้วย

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

  • ทำเครื่องหมายจำนวนประกอบด้วยตะแกรง
  • นับค่าที่ถูกทำเครื่องหมายภายในช่วง
  • จัดการช่วงว่างและจำนวน 0 กับ 1

โจทย์

จาก 1 ถึง 100 มีจำนวนเฉพาะกี่ตัว แล้วจาก 50 ถึง 60 ล่ะ ให้นับจำนวนเฉพาะ p ที่ low ≤ p ≤ high อย่าลืมว่า 0 และ 1 ไม่ใช่จำนวนเฉพาะ การใช้ตะแกรงจนถึง high จะตอบคำถามนี้ได้อย่างรวดเร็ว

จงเขียนฟังก์ชัน count_primes_in_range(low, high)

อินพุต

low: ขอบล่าง (รวมค่านี้ด้วย)

high: ขอบบน (รวมค่านี้ด้วย)

เอาต์พุต

คืนค่าจำนวนของจำนวนเฉพาะในช่วงนี้ ถ้า low > high ช่วงนี้จะว่างเปล่าและคำตอบคือ 0

เงื่อนไข

0 ≤ low ≤ 1,000,000

0 ≤ high ≤ 1,000,000

ตัวอย่าง

ตัวอย่างที่ 1
อินพุต:
low = 1
high = 100

ผลลัพธ์ที่คาดหวัง:
expected = 25
อินพุต:
long long low = 1;
long long high = 100;

ผลลัพธ์ที่คาดหวัง:
long long expected = 25;
อินพุต:
long low = 1;
long high = 100;

ผลลัพธ์ที่คาดหวัง:
long expected = 25;

คำอธิบาย

จำนวนเฉพาะที่ไม่เกิน 100 มีทั้งหมด 25 ตัว (2, 3, 5, … 97) คำตอบจึงเป็น 25

ตัวอย่างที่ 2
อินพุต:
low = 50
high = 60

ผลลัพธ์ที่คาดหวัง:
expected = 2
อินพุต:
long long low = 50;
long long high = 60;

ผลลัพธ์ที่คาดหวัง:
long long expected = 2;
อินพุต:
long low = 50;
long high = 60;

ผลลัพธ์ที่คาดหวัง:
long expected = 2;

คำอธิบาย

ระหว่าง 50 ถึง 60 มีเพียง 53 และ 59 ที่เป็นจำนวนเฉพาะ คำตอบจึงเป็น 2

แนวทางการแก้

ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ

คำใบ้ 1

สร้างตะแกรงจนถึง high โดยขีดฆ่าพหุคูณของจำนวนเฉพาะแต่ละตัว เริ่มจากกำลังสองของมัน

คำใบ้ 2

จากนั้นนับจำนวนที่ยังถูกทำเครื่องหมายว่าเป็นจำนวนเฉพาะตั้งแต่ low ถึง high

คำใบ้ 3

ถ้า low มากกว่า high ก็ไม่ต้องคำนวณอะไรเลย

ความซับซ้อนที่คาดหวัง

เวลา O(high log log high), หน่วยความจำเพิ่ม O(high)

แหล่งอ้างอิง

โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน

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

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

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

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

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