【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; } }