A問題 Strings
|
1 2 |
s,t = input().split() print(t+s) |
C – Next Prime
方針
・エラトステネスの篩によって素数のリストを作成する
・素数のリストの中から、初めて入力値x以上になった数字を出力する
解答
コード＋コメント
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
#素数のリストを返す関数 def Prime_List(limit): #素数のリスト prime_list = [] #limitまでの素数をbool値で保持するリスト prime_check_list = [True]*(limit) #0,1をFalseに初期設定 prime_check_list[0] = False prime_check_list[1] = False #素数判定 for i in range(limit): #iまでの数字の倍数であれば処理しない if not prime_check_list[i]: continue #1を除くiまでのどの数の倍数でもなければ素数リストに追加 prime_list.append(i) #iの2乗からスタートし、iずつ増えてlimit値まで篩にかける for j in range(i**2,limit,i): #iの倍数をFalseに変更し、篩にかける prime_check_list[j]=False #print(prime_list) #print(prime_check_list) return prime_list #入力 x = int(input()) #素数判定の上限：どの値まで素数であるかを調べるかを設定 limit = 10**7+1 #素数のリストを作成 prime_list = Prime_List(limit) #素数のリストの中でx以上の数字を出力 for k in prime_list: if k>=x: print(k) exit() |
コードのみ
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
def Prime_List(limit): prime_list = [] #limitまでの素数をbool値で保持するリスト prime_check_list = [True]*(limit) prime_check_list[0] = False prime_check_list[1] = False for i in range(limit): if not prime_check_list[i]: continue prime_list.append(i) for j in range(i**2,limit,i): prime_check_list[j]=False return prime_list x = int(input()) limit = 10**7+1 prime_list = Prime_List(limit) for k in prime_list: if k>=x: print(k) exit() |
参考
エラトステネスの篩について非常にわかりやすく説明されています。
本当は遅い「似非エラトステネスの篩」の罠 (zenn.dev)
その他
ABC解説記事一覧はこちら
コメント