[Python Python]伯俊1990号の少数のパリン・ドロンプ
12217 ワード
これは白準1990号の少数のパリンドロンの問題です.
少数の問題を見ると、私はいつもまずエラトネスのふるいを考えています.
もしあなたがエラトネスのふりをしたら、あなたは考えます.
primes = [False, False] + [True] * (n-1)
for i in range(2, n+1):
if primes[i]:
print(i)
for j in range(2*i, n+1, i):
primes[j] = Falseとりあえずこれでぐるっと回ると
パリンドロンを小数で形成した場合、偶数桁のパリンドロンの小数は「11」(?)にしか存在しないこれを使うと範囲を大きく縮小できることがわかります.
n, m = map(int, input().split())
if m >= 10000000:
m = 10000000
if 1000000 >= m >= 100000:
m = 100000
if 10000 >= m >= 1000:
m = 1000ここまでは、配列長を10,000,000個に減らしても当然タイムアウトします.
△一般的な問題は100万ぐらいあるはずです.
少数ながら偶数は‘2’のみ
primes = [False] + [True] * (m//2)
for i in range(1, len(primes)):
if primes[i]:
print(2*i+1)
for j in range(i + (2*i+1), len(primes), 2*i+1):
primes[j] = False今ここでパリンドロン検査をしましょう.
コード#コード#
def reverse(text):
result = ''
for t in text:
result = t + result
return result
n, m = map(int, input().split())
if m >= 10000000:
m = 10000000
if 1000000 >= m >= 100000:
m = 100000
if 10000 >= m >= 1000:
m = 1000
primes = [False] + [True] * (m//2)
for i in range(1, len(primes)):
if primes[i]:
if i*2 + 1 >= n and str(i*2+1) == reverse(str(i*2+1)):
print(2*i+1)
for j in range(i + (2*i+1), len(primes), 2*i+1):
primes[j] = False
print(-1)Reference
この問題について([Python Python]伯俊1990号の少数のパリン・ドロンプ), 我々は、より多くの情報をここで見つけました https://velog.io/@ashooozzz/Python-파이썬백준-1990번-소수인팰린드롬-풀이テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol