จำนวน Unusual (Unusual Number) คืออะไร?
จำนวน n ที่ ตัวหารเฉพาะมากที่สุด (largest prime factor) มากกว่า √n
สูตร: LPF(n) > √n
ตัวอย่าง
n = 14
- ตัวหารเฉพาะ: 2, 7
- มากที่สุด = 7
- √14 ≈ 3.74
- 7 > 3.74 → เป็น Unusual Number ✓
n = 12
- ตัวหารเฉพาะ: 2, 3
- มากที่สุด = 3
- √12 ≈ 3.46
- 3 < 3.46 → ไม่ใช่ Unusual ✗
Unusual Numbers ตัวแรกๆ
2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 20, 21, 22, 23, 26, 28, 29, 31, 33, 34, 35, 37, 38, 39, 41, 42, 43, 44, 46, ...
สังเกต: จำนวนเฉพาะทั้งหมดเป็น Unusual (เพราะ LPF = n > √n)
อัลกอริทึม
- หาตัวหารเฉพาะมากที่สุดของ n
- เปรียบเทียบกับ √n
ตัวอย่างโค้ด C++
#include <iostream>
#include <cmath>
using namespace std;
int largestPrimeFactor(int n) {
int maxPrime = -1;
// หาร 2 ออกไปก่อน
while (n % 2 == 0) {
maxPrime = 2;
n /= 2;
}
// หารเลขคี่จาก 3 ถึง sqrt(n)
for (int i = 3; i <= sqrt(n); i += 2) {
while (n % i == 0) {
maxPrime = i;
n /= i;
}
}
// ถ้า n ที่เหลือ > 2 แสดงว่าเป็นเฉพาะและมากกว่าที่เจอ
if (n > 2)
maxPrime = n;
return maxPrime;
}
bool isUnusual(int n) {
if (n <= 1) return false;
int lpf = largestPrimeFactor(n);
return lpf > sqrt(n);
}
int main() {
cout << "Unusual numbers up to 50: ";
for (int i = 2; i <= 50; i++)
if (isUnusual(i))
cout << i << " ";
cout << endl;
int test[] = {14, 12, 17, 100, 97};
for (int n : test) {
cout << n << " is " << (isUnusual(n) ? "" : "not ") << "unusual" << endl;
}
return 0;
}
ผลลัพธ์
Unusual numbers up to 50: 2 3 5 6 7 10 11 13 14 15 17 19 20 21 22 23 26 28 29 31 33 34 35 37 38 39 41 42 43 44 46 47 14 is unusual 12 is not unusual 17 is unusual 100 is not unusual 97 is unusual
คุณสมบัติทางคณิตศาสตร์
- ทุกจำนวนเฉพาะเป็น Unusual
- จำนวนประกอบที่เป็น Unusual ต้องมีตัวหารเฉพาะใหญ่ > √n → ตัวหารอีกตัวต้อง < √n
- ความหนาแน่นของ Unusual numbers เข้าใกล้ 1 (เกือบทุกตัวเป็น Unusual สำหรับ n ใหญ่)
