srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

ARC 044 A - 素数判定

問題

問題概要

Nが素数ならPrime
Nが合成数で, 1の位が2,5で割り切れず, 各桁の和が3で割り切れないとき, Prime
それ以外なら Not Prime

解法

まず, 普通に素数判定をし, 素数ならPrime.
次に, 1のくらいが2, 5で割り切れず, 各桁の和が3で割り切れないければ, Primeとして それ以外はNot Primeとなる.

ミス

各桁の和が3の倍数の時は, その数は3の倍数でした. 忘れてた.
N = 100a+10b + c = 99a + 9b + (a + b + c)
なので, a+b+c(各桁の和)が3の倍数であれば, 3の倍数となる. 各桁の和が9の倍数なら, 9の倍数でもあるのか.

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=n-1;i>=(0);i--)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define eall(v) unique(all(v), v.end())
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;


int main(void){
    string s; cin >> s;
    ll n = stoll(s);
    if(n == 1){
        printf("Not Prime\n"); return 0;
    }
    auto d = s.back() - '0';
    int sum = 0;
    bool f = true;
    for(auto u : s) sum += u - '0';
    for (int i = 2; i * i <= n; ++i){
        if(n % i == 0){
            f = false;
            break;
        }
    }
    if(f){
        printf("Prime\n"); return 0;
    }

    if((d % 2 != 0 && d != 5) && sum % 3 != 0){
        printf("Prime\n");
    }else{
        printf("Not Prime\n");
    }
    return 0;
}