少数(メスステロイド)

作成日:2022年1月7日午後5:17

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

# 소수(에라토스테네스 체)
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)

メスステロイド

nの最初の配列を作成し、各インデックスが小数の数であるかどうかを確認する必要があります.
このとき、すべてのセルがTrueとなり、基本的にはすべてのセルを少数として開始します.(逆も然り)
ループ文でTrue(少数)に遭遇すると、インデックス内のすべての倍数が少数ではないため、これらの倍数にアクセスして配列の値をFalseに変更できます.
最後までTrueのインデックス番号がnの少数であることを繰り返します.

覚えておきたいこと

Pythonを使用して実装される場合、コード

は、インデックスの倍数インデックスにアクセスする.

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

range()では、起点をi+i(2*i)とし、iの最初の倍数からnまで、iの値に近い.=iの倍数に近い.