posts - 99,  comments - 8,  trackbacks - 0
hud 1164 数论 将一个数分解成素因子之积
WA了一次，主要是自己把continue写成了break，所以遇到素数时下面的输就终止了；
解题思路：如n是素数就直接打印出来，如果不是素数(通过访问0--n下标的tag数组判断n是否为素数，再n依次对素数表prime【】求余求模分解n)，就利用打印出来的素数表进行不断地求余、求模分解；直到n为1；
一定要注意怎么输出哦！！！
 1#include <stdio.h>
 2#include <stdlib.h>
 3#define MAXSIZE 65535
 4int tag[MAXSIZE + 1];
 5int prime[MAXSIZE];
 6int cn ; 
 7
 8void 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
23int 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 雪黛依梦 阅读(400) 评论(0)  编辑 收藏 引用 所属分类: 数论

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


Copyright ©2024 雪黛依梦 Powered By: 博客园 模板提供：沪江博客
<2010年8月>
日一二三四五六
25262728293031
1234567
891011121314
15161718192021
22232425262728
2930311234

常用链接

留言簿(4)

随笔分类

随笔档案

文章档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜