ARC-044-A 素数判定

■■■問題■■■

高橋君は素数判定アルゴリズムが大好きです。
毎日さまざまな素数判定アルゴリズムを実装して遊んでいます。
しかし、高橋君は素数判定をしすぎてしまったので、素数判定に飽きてしまいました。
そこで高橋君は、「素数っぽく見える数」判定をすることにしました。 

1以上の整数Nは、以下のように「素数っぽい」かどうかが判定されます。
●Nが素数であるなら、Nは「素数っぽい」
●Nが合成数であるなら、Nを10進表記した時の1の位が偶数でも5でもなく、
  各桁の和が3で割り切れないならば、Nは「素数っぽい」
●それ以外の場合、Nは「素数っぽくない」

整数Nが与えられるので、
Nが「素数っぽい」場合は"Prime"、そうでない場合は"Not Prime"と出力してください。

■■■入力■■■

N

1行目には、整数N(1 <= N <= 10億)が与えられる。

■■■出力■■■

Nが「素数っぽい」場合は"Prime"、そうでない場合は"Not Prime"と出力せよ。
出力の末尾に改行を入れること。

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "Input1";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("42");
            //Not Prime
            //42は合成数かつ1の位が偶数なので、「素数っぽくない」と判定されます
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("49");
            //Prime
            //49は素数ではありませんが、「素数っぽい」と判定されます
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("3");
            //Prime
            //3は素数なので、「素数っぽい」と判定されます
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("1");
            //Not Prime
            //1は素数でも合成数でもないので、「素数っぽくない」と判定されます
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int N = int.Parse(InputList[0]);
        Console.WriteLine(IsSouuppoi(N) ? "Prime" : "Not Prime");
    }

    //素数っぽいかを判定
    static bool IsSouuppoi(int pN)
    {
        if (pN == 1) return false;

        if (IsPrime(pN)) {
            return true;
        }
        int Keta1 = pN % 10;
        if (Keta1 % 2 == 0) return false;
        if (Keta1 == 5) return false;

        int KetaSum = 0;

        while (pN > 0) {
            KetaSum += pN % 10;
            pN /= 10;
        }
        return KetaSum % 3 > 0;
    }

    //試し割りで素数かを判定
    static bool IsPrime(int pTarget)
    {
        if (pTarget == 2) return true;
        if (pTarget % 2 == 0) return false;
        for (int I = 3; I * I <= pTarget; I += 2) {
            if (pTarget % I == 0) return false;
        }
        return true;
    }
}

解説

最大でも10億なので、試し割りで素数判定しても、
ルート(10億)は、約3万なので、TLEにならないと判断してます。