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

จำนวนเฉพาะที่ตัดหลักได้

หาจำนวนเฉพาะที่ไม่เกินค่าที่กำหนดซึ่งยังคงเป็นจำนวนเฉพาะเมื่อตัดเลขโดดออกจากด้านใดด้านหนึ่ง

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

  • ตัดเลขโดดออกจากด้านใดด้านหนึ่งของจำนวน
  • ทดสอบทุกจำนวนที่ได้จากการตัด
  • เก็บผลลัพธ์เรียงตามลำดับ

โจทย์

ลองดู 3797 เมื่อตัดเลขโดดออกจากทางซ้ายจะได้ 797, 97 และ 7 เมื่อตัดออกจากทางขวาจะได้ 379, 37 และ 3 ทุกจำนวนเป็นจำนวนเฉพาะ และ 3797 เองก็เป็นจำนวนเฉพาะด้วย เราเรียกจำนวนเฉพาะแบบนี้ว่าจำนวนเฉพาะที่ตัดหลักได้ทั้งสองด้าน จำนวนเฉพาะหลักเดียวไม่มีหลักให้ตัดจึงไม่นับ ให้หาจำนวนเฉพาะที่ตัดหลักได้ทั้งสองด้านทุกตัวตั้งแต่ 10 ถึง limit

จงเขียนฟังก์ชัน truncatable_primes(limit)

อินพุต

limit: จำนวนที่มากที่สุดที่ต้องตรวจสอบ

เอาต์พุต

คืนค่าจำนวนเฉพาะเหล่านั้นเรียงจากน้อยไปมาก ถ้าไม่มีเลยให้คืนค่ารายการว่าง

เงื่อนไข

1 ≤ limit ≤ 100,000

ตัวอย่าง

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

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

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

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

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

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

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