โจทย์
A prime number is greater than 1 and divisible only by 1 and itself. Checking divisors up to the square root of n is enough.
Implement is_prime(n).
Input
n: The number to test.
Output
Return true if n is prime, otherwise false.
เงื่อนไข
-1,000 ≤ n ≤ 1,000,000,000,000
ตัวอย่าง
ตัวอย่างที่ 1
อินพุต:
n = 29
ผลลัพธ์ที่คาดหวัง:
expected = Trueอินพุต:
long long n = 29;
ผลลัพธ์ที่คาดหวัง:
bool expected = true;อินพุต:
long n = 29;
ผลลัพธ์ที่คาดหวัง:
bool expected = true;คำอธิบาย
29 has no divisors other than 1 and 29.
ตัวอย่างที่ 2
อินพุต:
n = 21
ผลลัพธ์ที่คาดหวัง:
expected = Falseอินพุต:
long long n = 21;
ผลลัพธ์ที่คาดหวัง:
bool expected = false;อินพุต:
long n = 21;
ผลลัพธ์ที่คาดหวัง:
bool expected = false;คำอธิบาย
21 = 3 × 7, so it is not prime.
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
Handle numbers below 2 first; they cannot be prime.
คำใบ้ 2
Test possible divisors only up to the square root of the number.
คำใบ้ 3
Watch out for even numbers and repeated factors, since one divisor is enough to disqualify primality.
ความซับซ้อนที่คาดหวัง
O(sqrt(n)) time, O(1) extra space
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน