將一個數值分解成兩個質數相乘

Question

我使用Borland C++ Builder
要寫一個程式如下:
使用者輸入一個4位數的數字為M

M=(q-1)*(p-1)

而q和p都必須為質數

目前我想到的是
先將M開根號再高斯

然後再繼續其他動作

不知道有沒有程式設計高手
會寫這一段程式?

我會非常感謝的!
這不算是我的作業~
是我研究演算法中的一個片段
所以希望如有老師級的 也一起給個意見喔
謝謝

M一定為偶數

Answer 1

重點: 四位數開根號必小於100
所以p, q 必小於100
底下就列舉重點的部分

/* 用陣列儲存 100 以內的質數 (共25個) */
prime_arr[] = {2, 3, 5, 7..., 97}

for (i = 1; i <= 25; i++)
{
j = prime_arr[i] - 1;
if (m % j = 0) /* 整除 */
{
n = m/j + 1; /* 另一數 */
for (k = 1; k <= 25; i++)
{
if (n = prime_arr[k]) break; /* 找到了 */
}
}
}
印出 (j+1) 和 n

/* 也可以先把 prime_arr 的值全部減1, 這樣可省去 +1, -1 的運算 */
/* prime_arr[] = {1, 2, 4, 6..., 96} */