結果
問題 | No.713 素数の和 |
ユーザー |
|
提出日時 | 2019-09-19 19:19:58 |
言語 | Nim (2.2.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,422 bytes |
コンパイル時間 | 3,596 ms |
コンパイル使用メモリ | 64,768 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-19 17:11:49 |
合計ジャッジ時間 | 4,705 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 6 |
ソースコード
import algorithm, math, systemconstwheel: array[1..8, int] = [4, 2, 4, 2, 4, 6, 2, 6]wheel_primes: array[1..8, int] = [7, 11, 13, 17, 19, 23, 29, 31]wheel_indices: array[1..31, int] = [0, 0, 0, 0, 0, 0, 0, 1, 1, 1,1, 2, 2, 3, 3, 3, 3, 4, 4, 5,5, 5, 5, 6, 6, 6, 6, 6, 6, 7,7]proc wheel_index(n: int): int =letd: int = (n - 1) div 30r: int = (n - 1) mod 30result = 8 * d + wheel_indices[r + 2]proc wheel_prime(n: int): int =letd: int = (n - 1) shr 3r: int = (n - 1) and 7result = 30 * d + wheel_primes[r + 1]proc primemask(limit: int): seq[bool] =letn: int = wheel_index(limit)m: int = wheel_prime(n)varsieve: seq[bool] = newSeq[bool](n + 1)p: intq: intj: intsieve.fill(true)for i in 1..wheel_index(sqrt(limit.float).int):if sieve[i]:p = wheel_prime(i)q = p ^ 2j = ((i - 1) and 7) + 1while q <= m:sieve[wheel_index(q)] = falseq += wheel[j] * pj = (j and 7) + 1return sieveproc prime(n: int): seq[int] =var ret: seq[int]if n >= 2: ret.add(2)if n >= 3: ret.add(3)if n >= 5: ret.add(5)if n < 7: return retvar sieve: seq[bool] = primemask(n)for i in 1..<sieve.len:if sieve[i]:ret.add(wheel_prime(i))return retimport strutilsletn: int = stdin.readline.parseIntans: int = sum(prime(n))echo ans