結果

問題 No.713 素数の和
ユーザー Grenache
提出日時 2018-09-16 19:10:27
言語 Java
(openjdk 23)
結果
AC  
実行時間 124 ms / 2,000 ms
コード長 2,888 bytes
コンパイル時間 3,496 ms
コンパイル使用メモリ 81,568 KB
実行使用メモリ 41,636 KB
最終ジャッジ日時 2024-07-18 07:28:17
合計ジャッジ時間 5,120 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 6
権限があれば一括ダウンロードができます

ソースコード

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

import java.io.*;
import java.util.*;
public class Main_yukicoder713 {
    private static Scanner sc;
    private static Printer pr;
    private static void solve() {
        int n = sc.nextInt();
        Prime prime = new Prime(n);
        int ans = 0;
        for (int p : prime) {
            ans += p;
        }
        
        pr.println(ans);
    }
    static class Prime implements Iterable<Integer> {
        private int n;
        private BitSet p;
        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));
                }
            }
        }
        boolean isPrime(int n) {
            if (n == 2) {
                return true;
            }
            if (n == 1 || (n & 0x1) == 0) {
                return false;
            }
            return !p.get(n / 2 - 1);
        }
        List<Integer> getPrimeList() {
            List<Integer> ret = new ArrayList<>();
            for (int p : this) {
                ret.add(p);
            }
            return ret;
        }
        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();
                    }
                }
            }
        }
        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(INPUT == null ? System.in : new ByteArrayInputStream(INPUT.getBytes()));
        pr = new Printer(System.out);
        solve();
//      pr.close();
        pr.flush();
//      sc.close();
    }
    static String INPUT = null;
    private static class Printer extends PrintWriter {
        Printer(OutputStream out) {
            super(out);
        }
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0