posts - 99, comments - 8, trackbacks - 0

WA了一次，主要是自己把continue寫成了break，所以遇到素?cái)?shù)時(shí)下面的輸就終止了；
解題思路：如n是素?cái)?shù)就直接打印出來，如果不是素?cái)?shù)(通過訪問0--n下標(biāo)的tag數(shù)組判斷n是否為素?cái)?shù)，再n依次對(duì)素?cái)?shù)表prime【】求余求模分解n)，就利用打印出來的素?cái)?shù)表進(jìn)行不斷地求余、求模分解；直到n為1；
一定要注意怎么輸出哦！！！

1

#include <stdio.h>
2

#include <stdlib.h>
3

#define MAXSIZE 65535
4

int tag[MAXSIZE + 1];
5

int prime[MAXSIZE];
6

int cn ;
7

8

void is_prime ()
9

{
10

for (int i = 2; i < MAXSIZE + 1; i ++)
11

{
12

if ( !tag[i] )
13

prime[cn++] = i;
14

for ( int j = 0 ; (j < cn) && ( i*prime[j] < MAXSIZE + 1 ) ; j ++ )
15

{
16

tag[ i * prime[j] ] = 1;
17

if ( i % prime [j] == 0)
18

break;
19

}
20

}
21

}
22

23

int main ()
24

{
25

is_prime ();
26

int n;
27

int elem[60000];
28

while ( scanf ("%d", &n) != EOF )
29

{
30

if ( !tag[n] )
31

{
32

printf ("%d\n",n);
33

continue;
34

}
35

else
36

{
37

int j = 0;
38

for (int i = 0; i < cn && n != 1 ; i ++)
39

{
40

while ( n % prime[i] == 0 )
41

{
42

elem[j] = prime[i];
43

n = n / prime[i];
44

j ++;
45

}
46

}
47

printf ("%d", elem[0]);
48

for (int m = 1; m < j; m++)
49

{
50

printf ("*%d",elem[m]);
51

}
52

printf ("\n");
53

}
54

}
55

//system ("pause");
56

return 0;
57

}
58

posted on 2010-08-06 09:19 雪黛依夢(mèng) 閱讀(415) 評(píng)論(0) 編輯收藏引用所屬分類: 數(shù)論

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
【推薦】100%開源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！

相關(guān)文章: HDU 1061 hdu 1021 HDU 1019 poj 1006 poj 1061 如何求求a * x + b * y = n的整數(shù)解（x y ）講解 gcd ( ) 和 ex—Gcd( ) HDU 1108 Gcd( ) 素?cái)?shù)的判定方法總結(jié) 中國(guó)剩余定理 hud 1164 數(shù)論將一個(gè)數(shù)分解成素因子之積

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理