ปานกลาง 0 ข้อที่แก้แล้ว อัตราผ่าน 0%

Truncatable Primes

List the primes up to a limit that stay prime as digits are removed from either end.

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

  • Remove digits from either end of a number
  • Test every truncation
  • Collect results in order

โจทย์

ดูฉบับแปล

Take 3797. Removing digits from the left gives 797, 97 and 7; removing them from the right gives 379, 37 and 3. All of them are prime, and so is 3797. Call such a prime two-sided truncatable. One-digit primes have nothing to remove and do not count. List every two-sided truncatable prime from 10 to limit.

Implement truncatable_primes(limit).

Input

limit: The largest number to check.

Output

Return the primes in increasing order. Return an empty list if there are none.

เงื่อนไข

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) both work; 13 fails because 1 is not prime and 29 fails because 9 is not. [23, 37].

ตัวอย่างที่ 2
อินพุต:
limit = 10

ผลลัพธ์ที่คาดหวัง:
expected = []
อินพุต:
long long limit = 10;

ผลลัพธ์ที่คาดหวัง:
std::vector<long long> expected = {};
อินพุต:
long limit = 10;

ผลลัพธ์ที่คาดหวัง:
long[] expected = new long[] {};

คำอธิบาย

Only one-digit primes are below 10 and they do not count: [].

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

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

คำใบ้ 1

Removing from the right is division by 10.

คำใบ้ 2

Removing from the left is taking the remainder modulo a power of 10.

คำใบ้ 3

Every truncation down to a single digit must be prime, and so must the number.

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

O(limit × d × √limit) time, O(answer) extra space

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

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

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

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

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

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

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