結果

問題 No.8023 素数判定するだけ
ユーザー mikitmikit
提出日時 2018-11-29 15:17:41
言語 Java21
(openjdk 21)
結果
WA  
実行時間 -
コード長 5,843 bytes
コンパイル時間 2,456 ms
コンパイル使用メモリ 78,772 KB
実行使用メモリ 44,376 KB
最終ジャッジ日時 2024-06-26 23:02:24
合計ジャッジ時間 8,297 ms
ジャッジサーバーID
(参考情報)
judge5 / judge2
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
権限があれば一括ダウンロードができます

ソースコード

diff #

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.UncheckedIOException;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author mikit
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        LightScanner in = new LightScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        No3030 solver = new No3030();
        solver.solve(1, in, out);
        out.close();
    }

    static class No3030 {
        private static final String YES = "YES";
        private static final String NO = "NO";

        public void solve(int testNumber, LightScanner in, PrintWriter out) {
            out.println(IntMath.isPrime(in.longs()) ? YES : NO);
        }

    }

    static final class IntMath {
        private IntMath() {
        }

        public static boolean isPrime(int n) {
            if (n == 2) {
                return true;
            } else if (n <= 1 || (n & 1) == 0) {
                return false;
            }
            int s = BitMath.lsb(n - 1);
            int d = (n - 1) >> s;
            ModMath m = new ModMath(n);
            outer:
            for (int a : new int[]{2, 7, 61}) {
                int r = (int) m.pow(a, d);
                if (r == 1 || r == n - 1) {
                    continue;
                }
                for (int j = 0; j < s; j++) {
                    r = (int) m.pow(r, 2);
                    if (r == n - 1) {
                        continue outer;
                    }
                }
                return false;
            }
            return true;
        }

        public static boolean isPrime(long n) {
            if (n == 2) {
                return true;
            } else if (n <= 1 || (n & 1) == 0) {
                return false;
            } else if (n < Integer.MAX_VALUE) {
                return isPrime((int) n);
            }
            int s = BitMath.lsb(n - 1);
            long d = (n - 1) >> s;
            ModMath m = new ModMath(n);
            outer:
            for (int a : new int[]{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) {
                long r = m.pow(a, d);
                if (r == 1 || r == n - 1) {
                    continue;
                }
                for (int j = 0; j < s; j++) {
                    r = m.pow(r, 2);
                    if (r == n - 1) {
                        continue outer;
                    }
                }
                return false;
            }
            return true;
        }

    }

    static class LightScanner {
        private BufferedReader reader = null;
        private StringTokenizer tokenizer = null;

        public LightScanner(InputStream in) {
            reader = new BufferedReader(new InputStreamReader(in));
        }

        public String string() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new UncheckedIOException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public long longs() {
            return Long.parseLong(string());
        }

    }

    static final class BitMath {
        private BitMath() {
        }

        public static int count(int v) {
            v = (v & 0x55555555) + ((v >> 1) & 0x55555555);
            v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
            v = (v & 0x0f0f0f0f) + ((v >> 4) & 0x0f0f0f0f);
            v = (v & 0x00ff00ff) + ((v >> 8) & 0x00ff00ff);
            v = (v & 0x0000ffff) + ((v >> 16) & 0x0000ffff);
            return v;
        }

        public static int count(long v) {
            v = (v & 0x5555555555555555L) + ((v >> 1) & 0x5555555555555555L);
            v = (v & 0x3333333333333333L) + ((v >> 2) & 0x3333333333333333L);
            v = (v & 0x0f0f0f0f0f0f0f0fL) + ((v >> 4) & 0x0f0f0f0f0f0f0f0fL);
            v = (v & 0x00ff00ff00ff00ffL) + ((v >> 8) & 0x00ff00ff00ff00ffL);
            v = (v & 0x0000ffff0000ffffL) + ((v >> 16) & 0x0000ffff0000ffffL);
            v = (v & 0x00000000ffffffffL) + ((v >> 32) & 0x00000000ffffffffL);
            return (int) v;
        }

        public static int lsb(int v) {
            if (v == 0) {
                throw new IllegalArgumentException("Bit not found");
            }
            v |= (v << 1);
            v |= (v << 2);
            v |= (v << 4);
            v |= (v << 8);
            v |= (v << 16);
            return 32 - count(v);
        }

        public static int lsb(long v) {
            if (v == 0) {
                throw new IllegalArgumentException("Bit not found");
            }
            v |= (v << 1);
            v |= (v << 2);
            v |= (v << 4);
            v |= (v << 8);
            v |= (v << 16);
            v |= (v << 32);
            return 64 - count(v);
        }

    }

    static class ModMath {
        private static final int DEFAULT_MOD = 1_000_000_007;
        private final long mod;

        public ModMath(long mod) {
            this.mod = mod;
        }

        public ModMath() {
            this(DEFAULT_MOD);
        }

        public long pow(long x, long y) {
            if (y == 0) {
                return 1;
            } else if (y % 2 == 0) {
                long z = pow(x, y / 2);
                return (z * z) % mod;
            } else {
                return (x % mod) * pow(x, y - 1) % mod;
            }
        }

    }
}

0