結果
問題 | No.713 素数の和 |
ユーザー |
|
提出日時 | 2018-07-24 10:14:53 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 1 ms / 2,000 ms |
コード長 | 936 bytes |
コンパイル時間 | 909 ms |
コンパイル使用メモリ | 117,384 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-13 01:31:56 |
合計ジャッジ時間 | 1,428 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 6 |
ソースコード
import std.algorithm, std.container, std.conv, std.math, std.range, std.typecons, std.stdio, std.string;auto rdsp(){return readln.splitter;}void pick(R,T)(ref R r,ref T t){t=r.front.to!T;r.popFront;}void readV(T...)(ref T t){auto r=rdsp;foreach(ref v;t)pick(r,v);}void main(){int n; readV(n);writeln(n == 1 ? 0 : primes(n).sum);}pure T[] primes(T)(T n){import std.algorithm, std.bitmanip, std.conv, std.range;auto sieve = BitArray();sieve.length((n+1)/2);sieve = ~sieve;foreach (p; 1..((nsqrt(n)-1)/2+1))if (sieve[p])for (auto q = p*3+1; q < (n+1)/2; q += p*2+1)sieve[q] = false;auto r = sieve.bitsSet.map!(to!T).map!("a*2+1").array;r[0] = 2;return r;}pure T nsqrt(T)(T n){import std.algorithm, std.conv, std.range, core.bitop;if (n <= 1) return n;T m = T(1) << (n.bsr/2+1);return iota(1, m).map!"a*a".assumeSorted!"a <= b".lowerBound(n).length.to!T;}