AOJ-ICPC 1154

前に解いた問題をメモっておくのを忘れていた。

Monday-Saturday Prime Factors | Aizu Online Judge
まとめるとだいたいこんな感じの問題↓

• ７で割った時のあまりが１または６の数字を「Monday-Saturday number」とよぶ
• Monday-Saturday numberのうち、その数字と１以外のMonday-Satureday numberでは割り切れない数字のことを「Manday-Saturday Prime」とよぶ（例:27）
• あるManday-Saturday numberであるbについて、あるManday-Saturday primeであるaで割り切れる時「aはbのMonday-Saturday prime factorである」という（例: 27は216のMonday-Saturday prime factor）

問題:入力されたMonday-Saturday numberのMonday-Saturday prime factorを求めよ。

こんな感じのコードを書いた。

#include <cstdio>
#include <iostream>
#include <cmath>
#include <ctype.h>
#include <string> 
#include <sstream>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
  
using namespace std;
 
bool isprime(int n);
  
int main()
{
   int n;
   while(1){
    cin >> n;
    if(n == 1) break;
    cout << n << ':';
    for(int i = 0; i <= n / 7; i++){
        int divisor = 0;
        if(n % (7 * i + 1) == 0){
            divisor = 7 * i + 1;
            if(isprime(divisor)) cout << ' ' << divisor;
        } 
        if(n % (7 * i + 6) == 0){
            divisor = 7 * i + 6;
            if(isprime(divisor)) cout << ' ' << divisor;
        } 
    }
        cout << endl;
    }
    return 0;
}
 
bool isprime(int n)
{
    if(n == 1) return false;
    else if(n == 6) return true;
    else if(n % 6 == 0) return false;
    else {
        for(int i = 1; 7 * i <= n; i++){
            if(n == 7 * i + 1) break;
            else if(n == 7 * i + 6){
                if(n % (7 * i + 1) == 0) return false;
                else return true;
            } else if(n % (7 * i + 1) == 0 || n % (7 * i + 6) == 0) return false;
        }
    }
    return true;
}

最初は「７で割ると余りが１〜６のどれかになる数字」だと勘違いしていたためうまくいかなかった。
間違いに気づいてからは、Monday-Saturday primeであるかの判定に苦労した。
結局1のとき、6のとき、6の倍数の時、それ以外の時と分けているけどもっとうまいやり方がありそう。
7 * i + 1, 7 * i + 6としているところを7 * i - 1、7 * i + 1とすればもっとうまく処理できそう。