Posted on 2010-08-06 09:18
MiYu 閱讀(531)
評論(1) 編輯 收藏 引用 所屬分類:
ACM ( 枚舉 ) 、
ACM ( 水題 ) 、
ACM ( 數論 )
//MiYu原創, 轉帖請注明 : 轉載自 ______________白白の屋題目地址:
http://acm.hdu.edu.cn/showproblem.php?pid=1164題目描述:
把一個數拆分成素數的乘積.
素數的水題 , 只要把素數提取出來, 暴力就可以了.
代碼如下 :
//MiYu原創, 轉帖請注明 : 轉載自 ______________白白の屋
#include <iostream>
using namespace std;
int num[70001];
int main ()
{
for ( int i = 2; i <= 70000; ++ i )
{
if ( !num[i] )
for ( int j = 2; i * j <= 70000; ++ j )
{
num[i*j] = 1;
}
}
int N;
while ( cin >> N )
{
int n = N;
int f = 1;
while ( n != 1 )
{
int i = 2;
for ( ; i <= 65535; ++ i )
{
if ( !num[i] && n % i == 0 )
{
if ( f )
{
cout << i;
f = 0;
}
else
{
cout << "*" << i;
}
break;
}
}
n /= i;
}
cout << endl;
}
// getchar();
return 0;
}