然後今天才解出來....
說明:
質數範圍為2~小於等於最大數的開根號向上取整的質數
此程式最大數為2,147,483,647,故其根號向上取整為46,341,程式中的數皆不會大於46,341。
如質數表中數字皆無法整除輸入資料,就可以判斷其為質數。
程式碼如下:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main()
{
int input[200000], input_count = 0, max = 0;
while(scanf("%d", &input[input_count]) != EOF)
{/* 讀取輸入 */
if(max < input[input_count])/* 判定最大數 */
max = input[input_count];
input_count++;/* 更新輸入資料數 */
}
int i
, max_sqrt = ((int)ceil(sqrt(max)))/* 最大數開根號,小數無條件進位 */
, table[max_sqrt]/* 確定質數表大小 */
, table_count = 0;/* 質數表資料數 */
table[table_count++] = 2;/* 先將2加入質數表中,並更新資料數 */
for(i = 3; i <= max_sqrt; i += 2)
{/* 只對奇數篩選,到最大數的開根號,建質數表 */
int j, flag = 0;
for(j = 0; j < table_count; j++)
{
if(i % table[j] == 0)
{/* 判斷新數字是否可以被質數表數字整除 */
flag = 1;
break;
}
}
if(!flag)
{/* 無法被整除,加入數質數表 */
table[table_count++] = i;/* 新數字加入質數表,並更新資料數 */
}
}
for(i = 0; i < input_count; i++)
{/* 處理輸入資料 */
int j, flag = 0;
for(j = 0; j < table_count &&input[i] > table[j] ; j++)
{/* 將輸入除以小於自身的質數 */
if(input[i] % table[j] == 0)
{/* 被整除,為合數,結束運算 */
flag = 1;
break;
}
}
if(flag)
{
printf("非質數\n");
}
else
{
printf("質數\n");
}
}
return 0;
}