fc2ブログ



Monday-Saturday Prime Factors

2008.07.10 22:54  ACM/ICPC 2008

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1154




001 #include<iostream>
002 using namespace std;
003 #define MAX 300001
004
005 bool prime[MAX];
006
007 void generate(){
008 fill( prime, prime + MAX, false ) ;
009 for ( int i = 1, k = 0; i <= MAX; k++){
010 prime[i] = true;
011 i += ((k % 2 == 0) ? 5 : 2);
012 }
013 prime[1] = false;
014 for ( int i = 1, k = 0; i * i <= MAX; k++ ){
015 if ( prime[i] ) {
016 for ( int j = 2*i; j <= MAX; j += i ) prime[j] = false;
017 }
018 i += ((k % 2 == 0) ? 5 : 2);
019 }
020 }
021
022 main(){
023 generate();
024 int x;
025 while( cin >> x ){
026 if ( x == 1 ) break;
027 cout << x << ":";
028 for ( int i = 1; i <= MAX; i++ ){
029 if ( prime[i] && x % i == 0 ) cout << " " << i;
030 }
031 cout << endl;
032 }
033 }


スポンサーサイト



テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |

この記事へのコメント

コメントを書く


管理人にのみ表示

↑ページトップ

この記事へのトラックバック

この記事にトラックバックする(FC2ブログユーザー)

↑ページトップ