結果

問題 No.843 Triple Primes
ユーザー Grenache
提出日時 2019-06-28 22:21:22
言語 Java
(openjdk 23)
結果
WA  
実行時間 -
コード長 3,785 bytes
コンパイル時間 3,823 ms
コンパイル使用メモリ 79,996 KB
実行使用メモリ 54,312 KB
最終ジャッジ日時 2024-07-02 04:52:58
合計ジャッジ時間 11,678 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 38 WA * 4
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import java.io.*;
import java.util.*;
public class Main_yukicoder843 {
    private static Scanner sc;
    private static Printer pr;
    private static void solve() {
        int n = sc.nextInt();
        
        if (n == 2) {
            pr.println(1);
        }
        
        Prime prime = new Prime(2 * n);
        long ans = 1;
        for (int r : prime) {
            if (r * r > 2 * n) {
                break;
            }
            if (r == 2) {
                continue;
            }
            int q = r * r - 2;
            if (q <= n && prime.isPrime(q)) {
                ans += 2;
            }
        }
        
        pr.println(ans);
    }
    /**
     * 素数リスト生成、素数判定、素因数分解などを行う
     */
    static class Prime implements Iterable<Integer> {
        private int n;
        private BitSet p;
        /**
         * 上限 n までの素数を保持するインスタンスを返す
         * O(n log log n)
         * 
         * @param n 保持する素数の上限
         */
        Prime(int n) {
            this.n = n;
            p = new BitSet(n / 2);
            int m = (int)Math.sqrt(n);
//          for (int i = 1; i <= m; i++) {
            for (int bi = p.nextClearBit(0); 2 * (bi + 1) + 1 <= m; bi = p.nextClearBit(bi + 1)) {
                long i = bi + 1;
//              if (p.get(i - 1)) {
//                  continue;
//              }
                for (long j = 2 * i * (i + 1); 2 * j + 1 <= n; j += 2 * i + 1) {
                    p.set((int)(j - 1));
                }
            }
        }
        /**
         * 素数かどうかを判定する
         * O(1)
         * 
         * @param n 判定する値
         * @return 素数の場合、true
         */
        boolean isPrime(int n) {
            if (n == 2) {
                return true;
            }
            if (n == 1 || (n & 0x1) == 0) {
                return false;
            }
            return !p.get(n / 2 - 1);
        }
        /**
         * 素数を含む List を返す
         * O(pi(n)) (pi(n):nまでの素数の個数)
         * 
         * @return n 以下の素数を含む List
         */
        List<Integer> getPrimeList() {
            List<Integer> ret = new ArrayList<>();
            for (int p : this) {
                ret.add(p);
            }
            return ret;
        }
        /**
         * 素因数分解の結果を返す
         * O(pi(n^1/2))?
         * 
         * @param x 素因数分解をする値
         * @return 素因数分解した結果
         */
        Map<Long, Integer> primeFactorize(long x) {
            Map<Long, Integer> hm = new TreeMap<>();
            long n = x;
            for (int p : this) {
                if ((long)p * p > n) {
                    break;
                }
                int cnt = 0;
                while (n % p == 0) {
                    cnt++;
                    n /= p;
                }
                if (cnt > 0) {
                    hm.put((long)p, cnt);
                }
            }
            if (n != 1) {
                hm.put(n, 1);
            }
            return hm;
        }
        @Override
        public Iterator<Integer> iterator() {
            return new PrimeIterator();
        }
        private class PrimeIterator implements Iterator<Integer> {
            int index;
            PrimeIterator() {
                index = -1;
            }
            @Override
            public boolean hasNext() {
                if (index == -1) {
                    return n >= 2;
                } else {
                    return 2 * (index + 1) + 1 <= n;
                }
            }
            @Override
            public Integer next() {
                if (index == -1) {
                    if (n >= 2) {
                        index = p.nextClearBit(0);
                        return 2;
                    } else {
                        throw new NoSuchElementException();
                    }
                } else {
                    int ret = 2 * (index + 1) + 1;
                    if (ret <= n) {
                        index = p.nextClearBit(index + 1);
                        return ret;
                    } else {
                        throw new NoSuchElementException();
                    }
                }
            }
        }
        /**
         * 素数かどうかを判定する(long)
         * O(n^1/2)
         * 
         * @param n 判定する値
         * @return 素数の場合、true
         */
        static boolean isPrime(long n) {
            if (n == 2) {
                return true;
            }
            if (n == 1 || (n & 0x1) == 0) {
                return false;
            }
            for (long i = 3; i * i <= n; i += 2) {
                if (n % i == 0) {
                    return false;
                }
            }
            return true;
        }
    }
    // ---------------------------------------------------
    public static void main(String[] args) {
        sc = new Scanner(System.in);
        pr = new Printer(System.out);
            
        solve();
            
        pr.close();
        sc.close();
    }
    static class Printer extends PrintWriter {
        Printer(OutputStream out) {
            super(out);
        }
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0