AOJ 1154: Monday-Saturday Prime Factors

問題

Monday-Saturday Prime Factors | Aizu Online Judge

  • 7で割った余りが1または6の数をMonday-Saturday numberと呼ぶ
  • Monday-Saturday numberが与えられたとき、それを割り切るMonday-Saturday prime (Monday-Saturday numberにおける素数）を全て求めよ

方針

Monday-Saturday numberを最初に列挙して、Monday-Saturday number版のエラトステネスのふるいを行う

コード

#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
#define rep(i, n) for(int i=0; i<(n); ++i)

const int MAX = 3000000;
int MonSat[MAX+1];
int isPrime[MAX+1];

int main(void){
    rep(i, MAX) MonSat[i] = (i%7==1 || i%7==6) ? 1 : 0;
    rep(i, MAX) isPrime[i] = (MonSat[i]==1) ? 1 : 0;
    for(int i=6; i<=MAX; ++i) {
        if(isPrime[i]==0) continue;
        for(int j=2; i*j<=MAX; ++j) {
            if(MonSat[j]) isPrime[i*j] = 0;
        }
    }
    int n;
    while(cin >> n && n!=1) {
        cout << n << ":";
        for(int i=2; i <= n; i++) {
            if(isPrime[i]==1 && n%i==0) {
                cout << " " << i;
            }
        }
        cout << endl;
    }
}

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1894777

反省