BOJ 1016平方ㄴ数

質問する

BOJ 1016平方ㄴ数
金色1|白駿1016|Python 3糸草

アルゴリズム#アルゴリズム#

受信入力

記録テストステロンのリストを生成(N~M+1)

1平方数がMAX未満まで繰り返す(インデックス変数i)

・j排水を作るための変数(i * i * j賈MAXそれ以下まで)

i * i * jインデックス範囲内であればアクセスをチェックし、世紀を数える

繰返し終了後、出力総数のうち訪問していない箇所の数(len(a) - count)

に質問
1)エラトネスの体を使わなければ→タイムアウト
2)テストステロンのふるいを使う→数字を含むリストを作成するか、リストの長さを0からMAXまでメモリを超える
3)リストを使用し、エラトネスのボディを使用する必要があります
4)アクセスチェックが必要であり,インデックス範囲を調整してチェックする必要がある(N~M+1)
→範囲を調整しないとタイムアウト
5)Cシリーズはint範囲外なので使用long longタイプ

コード#コード#

import sys

input = sys.stdin.readline

N, M = map(int, input().split())

# 에라토스테네스의 체 (소수면 True)
a = [True for _ in range(M - N + 1)]
count = 0
i = 1

# 에라토스테네스의 체
while i * i <= M:
    i += 1
    j = N // (i * i)
	
    while i * i * j <= M:
    	# i^2의 배수
        sq = i * i * j
			
        if sq >= N:
            if a[sq - N]:
                count += 1
                # 소수가 아니므로 체크
                a[sq - N] = False
        j += 1

print(len(a) - count)

結果

基本的な考え方は簡単ですが(エストラジオールを適用)
インデックス範囲を再調整してタイムアウトとメモリオーバーフローを削減
→メモリ消費量がより速く、より少ないミラー・ロビンの使用