少数(メスステロイド)

インプリメンテーションコード

# 소수(에라토스테네스 체)
import sys
sys.stdin = open("input.txt", "rt")
n = int(input())
numList = [True] * n

# n의 최대 약수는 sqrt(n) 이하이다 => i = sqrt(n)까지 검사
m = int(n ** 0.5)
for i in range(2, m+1):
    if numList[i] == True:
        for j in range(i+i, n, i): # i의 배수들은 소수가 아니기 때문에 전부 False로 수정
            numList[j] = False

primeList = [i for i in range(2,n) if numList[i] == True]

if (n == 2):
    print(1)
else:
    print(len(primeList))

母の答え

import sys
#sys.stdin=open("input.txt", "r")
n=int(input())
ch=[0]*(n+1)
cnt=0
for i in range(2, n+1):
    if ch[i]==0:
        cnt+=1
        for j in range(i, n+1, i):
            ch[j]=1
print(cnt)

メスステロイド

覚えておきたいこと

for i in range(2, m+1):
	for j in range(i+i, n, i): # i의 배수들은 소수가 아니기 때문에 전부 False로 수정