結果

問題 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
0