結果

問題 No.713 素数の和
ユーザー varrho
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

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

import algorithm, math, system
const
wheel: 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 =
let
d: int = (n - 1) div 30
r: int = (n - 1) mod 30
result = 8 * d + wheel_indices[r + 2]
proc wheel_prime(n: int): int =
let
d: int = (n - 1) shr 3
r: int = (n - 1) and 7
result = 30 * d + wheel_primes[r + 1]
proc primemask(limit: int): seq[bool] =
let
n: int = wheel_index(limit)
m: int = wheel_prime(n)
var
sieve: seq[bool] = newSeq[bool](n + 1)
p: int
q: int
j: int
sieve.fill(true)
for i in 1..wheel_index(sqrt(limit.float).int):
if sieve[i]:
p = wheel_prime(i)
q = p ^ 2
j = ((i - 1) and 7) + 1
while q <= m:
sieve[wheel_index(q)] = false
q += wheel[j] * p
j = (j and 7) + 1
return sieve
proc 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 ret
var sieve: seq[bool] = primemask(n)
for i in 1..<sieve.len:
if sieve[i]:
ret.add(wheel_prime(i))
return ret
import strutils
let
n: int = stdin.readline.parseInt
ans: int = sum(prime(n))
echo ans
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0