[伯俊]11653 Python(分解素数)
タイムアウトコード
n = int(input())
list = []
#n보다 작은 소수들을 리스트에 넣기
for i in range(2, n+1):
for j in range(2,int(i**0.5)+1):
if i%j==0:
break
else:
list.append(i)
#n이 소수로 나눠지면 나누기 (n이 1이 될 때까지 반복)
while n!=1:
for i in list:
if n%i == 0:
n = n/i
print(i)
break
に答える
nを入力します
nより小さい少数の人をリストに入れる.
for j in range(2,int(i**0.5)+1):
if i%j==0:
break
else:
list.append(i)
ここでfor文の範囲が2からint(i**0.5)+1である理由はいくつかの自然数では、約数の個数は平方根に準じて対称であるからである.
例えば、12の約数は、1、2、3、4、6、12(6個)である.
ルート番号12(=3.xx)より釘の数は3個、大きい数は3個です.
次にnを小数で割ってnが1になるまで.
しかし、このようにして結果はタイムアウトしました.
正しいコード
n = int(input())
i = 2
while n!=1:
if n%i == 0:
print(i)
n = n/i
else:
i+=1
小数点を探さなければならない.
「分かち合う最小数」を求めればいい.
Reference
この問題について([伯俊]11653 Python(分解素数)), 我々は、より多くの情報をここで見つけました https://velog.io/@0sunset0/백준-11653-파이썬-소인수분해テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol