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