ICPC 国内予選2008B 月曜土曜素因数 AOJ 1154

解法：月曜土曜素数でエラトステネスをやる。
問題文の日本語を読解するのがvery hard。そのほかはeasy。

#include <bits/stdc++.h>
#include <map>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;
 
typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;
 
const ll MOD=1e9+7;
const ll INF=1e18;
 
int dx[]={1, -1, 0, 0};
int dy[]={0, 0, 1, -1};


bool prime[300100];
int p[] = {1,6};

int main(){
    prime[6] = true;
    for(int k = 0;k < 2;k++){
        for(int i = 1;7*i+p[k] < 300000;i++){
            prime[7*i+p[k]] = true;
        }
    }

    for(int i = 0;7*i+1 < 300000;i++){
        for(int j = 0;j < 2;j++){
            int num = 7*i+p[j];
            if(num == 1 || prime[num] == false)continue;
            for(int jj = 0;jj < 2;jj++){
                for(int ii = 0;(7*ii+p[jj])*num < 300000;ii++){
                    int num2 = (7*ii+p[jj])*num;
                    if(num2 == num) continue;
                    prime[num2] = false;
                }
            }
        }
    }

    int n;
    while(true){
        cin >> n;
        if(n == 1) break;
        cout << n << ":";
        for(int i = 2;i <= n;i++){
            if(prime[i] == false || n % i != 0) continue;
            if( ((n/i)-1)%7 == 0 || ((n/i)-6)%7 == 0) cout << " " << i;
        }
        cout << endl;
    }
}