โจทย์
การหมุนจำนวนคือการย้ายเลขโดดตัวแรกไปไว้ท้ายสุด เช่น 197 กลายเป็น 971 แล้วเป็น 719 จำนวนเฉพาะจะเป็นจำนวนเฉพาะแบบวงกลมเมื่อจำนวนที่ได้จากการหมุนทุกแบบเป็นจำนวนเฉพาะด้วย ดังนั้น 197 เป็นจำนวนเฉพาะแบบวงกลม ให้นับจำนวนเฉพาะแบบวงกลมตั้งแต่ 2 ถึง limit จำนวนที่ได้จากการหมุนอาจมากกว่า limit ได้ แต่ก็ยังต้องเป็นจำนวนเฉพาะ
จงเขียนฟังก์ชัน circular_primes(limit)
อินพุต
limit: จำนวนที่มากที่สุดที่ต้องตรวจสอบ
เอาต์พุต
คืนค่าจำนวนของจำนวนเฉพาะ p ≤ limit ที่เป็นจำนวนเฉพาะแบบวงกลม
เงื่อนไข
1 ≤ limit ≤ 100,000
ตัวอย่าง
อินพุต:
limit = 20
ผลลัพธ์ที่คาดหวัง:
expected = 7
อินพุต:
long long limit = 20;
ผลลัพธ์ที่คาดหวัง:
long long expected = 7;
อินพุต:
long limit = 20;
ผลลัพธ์ที่คาดหวัง:
long expected = 7;
คำอธิบาย
2, 3, 5, 7, 11, 13 (31 เป็นจำนวนเฉพาะ) และ 17 (71 เป็นจำนวนเฉพาะ) เป็นจำนวนเฉพาะแบบวงกลม แต่ 19 ไม่ใช่ (91 = 7 × 13) คำตอบจึงเป็น 7
อินพุต:
limit = 1
ผลลัพธ์ที่คาดหวัง:
expected = 0
อินพุต:
long long limit = 1;
ผลลัพธ์ที่คาดหวัง:
long long expected = 0;
อินพุต:
long limit = 1;
ผลลัพธ์ที่คาดหวัง:
long expected = 0;
คำอธิบาย
ไม่มีจำนวนเฉพาะที่ไม่เกิน 1 คำตอบจึงเป็น 0
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
การหมุนหนึ่งครั้งคือย้ายเลขโดดตัวแรกไปไว้ท้าย จำนวน d หลักจึงหมุนได้ d แบบ
คำใบ้ 2
การแปลงจำนวนเป็นสตริงทำให้หมุนได้ง่าย
คำใบ้ 3
จำนวนที่ได้จากการหมุนอาจมากกว่า limit จึงต้องทดสอบความเป็นจำนวนเฉพาะโดยตรง
ความซับซ้อนที่คาดหวัง
เวลา O(limit × d × √(10^d)) เมื่อใช้การหารทดลอง, หน่วยความจำเพิ่ม O(d)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน