C++ 素數與二進制關係探討：素數二進制特徵與除 sqrt 外的判斷算法

素數二進制特徵

• 最低位恆為 1：除 2 外所有素數為奇數，二進制最低位必為 1。
• 無固定規律：高位分布看似隨機，無簡單位模式可直接判斷素性（否則破解 RSA 等加密）。
• 梅森素數：形如 2^p - 1 的素數，二進制全為 1（如 3=11, 7=111, 31=11111），但此類極稀少。

常用素數判斷算法（不依賴 sqrt）

初學者建議

1. 先掌握 試除法 + √n 優化，理解循環不變量與提前退出。
2. 實現 篩法 解決「100 以內素數」等批量問題。
3. 嘗試實現 Miller-Rabin（網上有成熟 C++ 模板），體會概率算法思想。
4. 少用現成庫函數，手寫核心邏輯才能建立扎實基本功。