[伯俊]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
  • 回答
    小数点を探さなければならない.
    「分かち合う最小数」を求めればいい.