ACM-ICPC 「月曜土曜素因数」

2008のB問題です。

問題
Monday-Saturday Prime Factors | Aizu Online Judge
素数とは、「１と自分以外に約数を持たないもの」です。普段はこれを「すべての自然数」について考えていますが、これを「７で割ると１または６余る数の集合」に絞って考えるとどうなるかという問題です。

解説
この問題は以下のステップを踏みます。
１　「７で割ると１または６余る数の集合」を作る（月曜土曜数の配列　ms）
２　作った集合を元に、月曜土曜素数の集合をさらに作る　（月曜土曜素数の配列　msprime）
３　各入力に対して月曜土曜素数で割っていき、素因数になるかどうか調べる（月曜土曜素因数）

ステップ１
今回、与えられるq個のデータの上限は高々300000未満であることに注意です。
７で割ると１または６余る集合は、
・( i % 7==1 || i % 7==6) となるような i を集める
・iを増やしながら、7 * i + 1 と 7 * i + 6 を集める
で作ることができます。僕は後者で行い、msという配列に格納しました。

ステップ２
素数判定をするにあたり、
・Nの素数が存在する時、ルートN 以下しかの値しか存在しない
ということは必須です。

よって、すべての月曜土曜数 ms[i] について、sqrt(ms[i]) 以下のms[j]で割っていき、一度も割りきれなければそれは月曜土曜素数です。これをmsprime[] に格納します。

スッテプ３
入力に対して、msprime[i] で割ってみて、割り切れたらその都度出力します。

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <utility>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <cmath>
 
#define rep(i,j,k) for(int i=(int)j;i<(int)k;i++)
#define itrep(i,x) for(auto i=(x).begin(); i!=(x).end();i++)
#define Sort(x) sort((x).begin(),(x).end())
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define vec vector
#define INF INT_MAX
#define INFL 1e18
#define MOD 1000000007
#define pb push_back
#define MP make_pair
#define PI 3.1415926535
typedef long long int ll;
typedef std::pair<int,int> P;
int D=1;
int dx[4]={0,1,0,-1},dy[4]={-1,0,1,0};
 
using namespace std;
 
int main(){
　//msが月曜土曜数、msprimeが月曜土曜素数
    vector<int> ms,msprime;
 
        //ステップ１
        for(int i=0;;i++){
            if(i==0)ms.pb(7*i+6); //１は月曜土曜数にはならない
            else {
                if(7*i+1>=300000)break;
                ms.pb(7*i+1);
                ms.pb(7*i+6);
            }
        }
         
        //ラムダ式を使って、月曜土曜素数の判定関数を作る
        auto isPrime=[&](int x){
            for(int i=0;(ms[i]<=sqrt(x)+1);i++){
                if(x%ms[i]==0){
                    return false;
                }
            }
            return true;
        };
        
　　//msprimeに素数を格納する
        rep(i,0,ms.size()){
            if(isPrime(ms[i])) msprime.pb(ms[i]);
        }
 
 
    int n;
    while(cin>>n && n!=1){
        cout<<n<<":";
 
        rep(i,0,msprime.size()){
            if(n%msprime[i]==0){  msprime[i]で割れたらその都度出力
                cout<<" "<<msprime[i];
            }
        }
        cout<<endl;
 
    }
 
    return 0;
}