MondaySaturdayPrimeFactors.cpp

#include <iostream>
#include <sstream>
#include <string>
#include <cmath>
#include <cstdio>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <numeric>
using namespace std;

// smp : 月曜土曜数
// (7の余り{0,1,2,3,4,5,6} * 月曜土曜数の余り{1,6}) (mod 7)
//        を全て試してみる．

// 0 * 6 == 0
// 0 * 1 == 0
// 1 (smp) * 6 == 6 -> smp
// 1 (smp) * 1 == 1 -> smp
// 2 * 6 == 5
// 2 * 1 == 2
// 3 * 6 == 4
// 3 * 1 == 3
// 4 * 6 == 3
// 4 * 1 == 4
// 5 * 6 == 2
// 5 * 1 == 5
// 6 (smp) * 6 == 1 -> smp
// 6 (smp) * 1 == 6 -> smp

// 以上より，月曜土曜数の約数が存在するとき，それは月曜土曜数である．
// だから，月曜土曜素数の判定は月曜土曜数の倍数の数を消していくので十分である．

bool smp[300001];

int main(){

  for(int i=0;i<300001;i++){ //月曜土曜数の判定
        if((i%7==1)||(i%7==6)) smp[i] = true;
        else smp[i] = false;
    }

    smp[1] = false;

    for(int i=0;i<300001;i++){ //月曜土曜素数の判定
        if(smp[i]){
            for(int j = i*2; j < 300001;j = j + i){
	      if(smp[j]) smp[j] = false;
            }
        }
    }
    int n = 0;
    while(1){
    	cin >> n;
    	if (n == 1) break;
        cout << n << ':';
        for(int i=0;i<n+1;i++){// nの約数かつ月曜土曜素数であるものを出力
	  if(smp[i] && !(n % i)) cout << ' ' << i;
        }
	cout << endl;
    }
}