โจทย์
ลองดู 3797 เมื่อตัดเลขโดดออกจากทางซ้ายจะได้ 797, 97 และ 7 เมื่อตัดออกจากทางขวาจะได้ 379, 37 และ 3 ทุกจำนวนเป็นจำนวนเฉพาะ และ 3797 เองก็เป็นจำนวนเฉพาะด้วย เราเรียกจำนวนเฉพาะแบบนี้ว่าจำนวนเฉพาะที่ตัดหลักได้ทั้งสองด้าน จำนวนเฉพาะหลักเดียวไม่มีหลักให้ตัดจึงไม่นับ ให้หาจำนวนเฉพาะที่ตัดหลักได้ทั้งสองด้านทุกตัวตั้งแต่ 10 ถึง limit
จงเขียนฟังก์ชัน truncatable_primes(limit)
อินพุต
limit: จำนวนที่มากที่สุดที่ต้องตรวจสอบ
เอาต์พุต
คืนค่าจำนวนเฉพาะเหล่านั้นเรียงจากน้อยไปมาก ถ้าไม่มีเลยให้คืนค่ารายการว่าง
เงื่อนไข
1 ≤ limit ≤ 100,000
ตัวอย่าง
อินพุต:
limit = 40
ผลลัพธ์ที่คาดหวัง:
expected = [23, 37]
อินพุต:
long long limit = 40;
ผลลัพธ์ที่คาดหวัง:
std::vector<long long> expected = {23, 37};
อินพุต:
long limit = 40;
ผลลัพธ์ที่คาดหวัง:
long[] expected = new long[] {23, 37};
คำอธิบาย
23 (2, 3) และ 37 (3, 7) ใช้ได้ทั้งคู่ ส่วน 13 ไม่ผ่านเพราะ 1 ไม่ใช่จำนวนเฉพาะ และ 29 ไม่ผ่านเพราะ 9 ไม่ใช่จำนวนเฉพาะ คำตอบคือ [23, 37]
อินพุต:
limit = 10
ผลลัพธ์ที่คาดหวัง:
expected = []
อินพุต:
long long limit = 10;
ผลลัพธ์ที่คาดหวัง:
std::vector<long long> expected = {};
อินพุต:
long limit = 10;
ผลลัพธ์ที่คาดหวัง:
long[] expected = new long[] {};
คำอธิบาย
จำนวนที่น้อยกว่า 10 มีแต่จำนวนเฉพาะหลักเดียวซึ่งไม่นับ คำตอบจึงเป็น []
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
การตัดหลักทางขวาคือการหารด้วย 10
คำใบ้ 2
การตัดหลักทางซ้ายคือการหาเศษจากการหารด้วยกำลังของ 10
คำใบ้ 3
ทุกจำนวนที่ได้จากการตัดจนเหลือหลักเดียวต้องเป็นจำนวนเฉพาะ และตัวจำนวนเองก็ต้องเป็นด้วย
ความซับซ้อนที่คาดหวัง
เวลา O(limit × d × √limit), หน่วยความจำเพิ่ม O(answer)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน