日々精進

aikoと旅行とプログラミング

【AOJ 1154】Monday-Saturday Prime Factors

問題

Monday-Saturday Prime Factors | Aizu Online Judge

方針

月曜土曜数 a が月曜土曜数 b の月曜土曜約数であるための必要十分条件は, a が b の普通の意味の約数であること.
「エラトステネスの篩」の要領で月曜土曜素数を生成して試す.
出力のフォーマットミスに気づかず, プレゼンテーションエラーしまくった.

ソース

#include <iostream>
#include <vector>
#include <cmath>
#include <utility>

using namespace std;

bool prime[300001];

signed main(){
  int n;
  
  vector<int> nums;
  
  fill(prime, prime+300000, true);
  
  for(int i = 2 ; i <= sqrt(300000) ; i++){
    if((i%7 == 1 || i%7 == 6) && prime[i]){
      for(int j = i * 2 ; j <= 300000 ; j+=i){
        prime[j] = false;
      }
    }
  }
  
  for(int i = 2 ; i < 300000 ; i++){
    if(prime[i] && (i%7==1 || i%7 == 6)) {
      nums.push_back(i);
    }
  }

  while(cin >> n, n!=1){
    cout << n << ": ";
    vector<int> ans;
    for(int i = 0 ; i < (int)nums.size() && nums[i] <= n ; i++){
      if(n % nums[i] == 0){
        ans.push_back(nums[i]);
      }
    }

    for(int i = 0 ; i < (int)ans.size() - 1 ; i++){
      cout << ans[i] << " ";
    }
    cout << ans[(int)ans.size()-1] << endl;
  }
  
}