[アルゴリズム]白駿1929号小数を求める(Python)


白駿#1929


問題のショートカット

質問する


MまたはN以上のすべての小数を出力するプログラムを作成してください.

I/Oルール


1.入力
  • の第1行において、自然数MおよびNは、スペースを介して与えられる.(1≦M≦N≦1000000)M以上N以下の小数は1つ以上の入力のみを与える.
    2.出力
  • 行ごとに1つずつ、小数をインクリメント順に出力します.
  • 質問へのアクセス


    2つの自然数の間の小数を求める問題なので、まず小数を求める関数を書き出して、それから文を繰り返して2つの自然数の間の小数を求めればいいのです.素数を求める式では,mathモジュールのsqrt関数を用いて,入力数の平方根を検証するだけで時間複雑度O(n^1/2)を低減できる.

    問題解決(Python)

    
    import math
    
    a, b = map(int, input().split(" "))
    
    def check(num):
        if num == 1:
            return False
    
        else:
            for i in range(2, int(math.sqrt(num)+1)):
                if num%i == 0:
                  return False       
            
            return True
    
    for i in range(a, b+1):
        if check(i):
            print(i)