Problem:

C: 素数

問題

  ある日、素数が大好きなそすうさ君は $p + q$ が素数となるペア $(p, q)$ で遊んでいた。
  そすうさ君は突然、このペアのうち、 $p$ と $q$ がともに $N$ 以下の素数であるペアがいくつあるか気になりだした。
  そすうさ君に代わって個数を求めよ。

制約

  
入力値は全て整数である。

  
$1 \leq N \leq 10^7$

入力形式

 入力は以下の形式で与えられる。 

  $N$

出力

ペアの個数を出力せよ。また、末尾に改行も出力せよ。 

サンプル

サンプル入力 1

3

サンプル出力 1

2

ペアは $(2, 3), (3, 2)$ の二つである。

サンプル入力 2

20

サンプル出力 2

8



Sample input:
3


Sample output:
2

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    root = int(n ** (1 / 2)) + 1
    isPrime = [True] * (n + 3)
    for i in range(4, n + 3, 2):
        isPrime[i] = False
    
    ans = 0
    prePrime = -1
    for i in range(3, n + 3, 2):
        if isPrime[i]:
            if prePrime + 2 == i:
                ans += 2
                
            prePrime = i
            if i > root:
                continue
            for j in range(i * i, n + 3, i):
                isPrime[j] = False
    print(ans)

main()

Submission status: Accepted

Solution code:
import math

N = int(input())
P = [True for x in range(N + 3)]

P[0] = False
P[1] = False

for i in range(2, int(math.sqrt(N + 3)) + 1):
    if P[i]:
        for j in range(i * 2, N + 3, i):
            P[j] = False

count = 0

for q in range(3, N + 1):
    if P[q] and P[2 + q]:
        count += 2

print(count)