読者です 読者をやめる 読者になる 読者になる

SRM 677 Div2 Easy: PalindromePrime

SRM は何回かやってたけど初めてコンテスト中に提出できました…(easy のみ)。

250: PalindromePrime

区間 [L, R] のうちで、素数かつ後ろから読んでも同じ(回分みたいになってる)整数をカウントする。 本番ではエラトステネスのふるいを書いたけど素数判定と回文判定だけすればいいらしい。

class PalindromePrime {
    public:
        // 回文かどうか
        bool is_r(int s) {
            stringstream ss;
            ss << s;
            string a = ss.str();
            int n = a.size();
            for(int i=0; i<n; i++) {
                if(a[i] != a[n - 1 - i]) return false;
            }
            return true;
        }

        bool is_prime(int n) {
            for(int i=2; i*i <= n; i++)
                if(n % i == 0) return false;
            return n != 1;
        }

        int count(int L, int R) {
            int ans = 0;
            for(int i = max(2, L); i <= R; i++) {
                if(is_prime(i) and is_r(i)) ans++;
            }
            return ans;
        }
};

来年は本気を出して緑以上になりたい。