2010年6月17日 星期四

Problem 406 Prime Cuts,中間的質數

建立質數表後,再找尋左右兩側印出的點,然後印出就好了。

首先建立質數表,要注意要將 1 也加入,在此題 1 也為質數, C 語言程式碼如下:
#define MAXSIZE  1010

int prime[MAXSIZE + 1];
int prime_table[MAXSIZE], prime_table_len = 0;

int makeprime(){
int i, j;
prime_table[prime_table_len ++] = 1;
prime_table[prime_table_len ++] = 2;
for(i = 3; i <= MAXSIZE; i += 2)
if(!prime[i]){
for(j = i + i; j <= MAXSIZE; j += i)
prime[j] = 1;
prime_table[prime_table_len ++] = i;
}
}
輸入 n 值後,先找出小於等於 n 值得質數,再找出左右兩側印出的索引,最後利用這兩索引,印出在這兩索引之間的質數,C 語言程式碼如下:
while (scanf("%d %d", &n, &c) == 2)
{
for (len = 0; n >= prime_table[len]; len ++)
;
if (len % 2)
{
if ( (c * 2 - 1) >= len) left = 0, right = len - 1;
else left = len / 2 - (c - 1), right = len / 2 + (c - 1);
}
else
{
if ( c * 2 >= len) left = 0, right = len - 1;
else right = len / 2 + (c - 1), left = right - 2 * c + 1;
}
printf("%d %d:", n, c);
for (i = left; i <= right; i ++)
printf(" %d", prime_table[i]);
printf("\n\n");
}

By David.K

p406題目連結
回ACM題庫目錄
回首頁

6 則留言:

heartbeat_3578 提到...

請問要如何寫一ㄍ大數字用質數因數分解
再一個一個的printf出來?
例如:39=13*3
13跟3都是質數也是他的因數

heartbeat_3578 提到...

不好意思
我想在請問一下
我程式跑不出來
不知是啥問題??
我是用Devc++的程式去跑
但是我有設定適用c語言跑的說!!
可以幫我解惑一下嗎?

David Kuo 提到...

請問您說的大數,是指超出 long long int 型態的範圍嗎?如果超出這型態的整數,要去做質因數分解,對我來說,那還蠻棘手的。
你說 Dev C++ 跑不出來,是不是因為你沒有執行(寫好之後直接按下 "F9" 鍵)?因為我灌 Dev C++ 幾乎不用設定就可以執行,說不定你沒有匯入檔案(例如:#include <stdio.h> 沒加上)。如果可以的話,再詳細敘述您的狀況。

heartbeat_3578 提到...

請問要怎嚜在哪個地方加入?
printf("\n Enter any number -> =")

heartbeat_3578 提到...

我真的忘了要加上這個地方int main(){}
但是我不知道要如何加上
printf("\n Enter any number n= ");
要在哪個地方加上??

David Kuo 提到...

#include <stdio.h>
#include <stdlib.h>

int main()
{
printf("\n Enter any number -> ="); /* 印出 */
system("pause"); /* 暫停程式 */
return 0;
}
或許是程式執行太快您沒有看到,或許是有其他方面的問題,不過上面您複製後貼到您的程式碼上再執行,您應該看的到結果。