#ABC149 Next Prime
素数判定をしよう．
もちろんライブラリを使ったり，ネットに載ってるアルゴリズムを使ったりしてもよいのですが，自分の実力で勝負するのも大切かなと最近は思っております．
というわけで今回は実力そのまま，プロのプログラマーが見たら卒倒するようなコードで挑むことにしました．
from sys import stdin
input=stdin.readline
def isPrime(x):
for div in range(2, x // 2 + 1):
if x % div == 0:
return False
return True
X = int(input())
if isPrime(X):
print(X)
exit()
while (X < 10 ** 5):
X+=1
if isPrime(X):
print(X)
exit()
#100000より大きい素数のうち最小のもの
print(100003)
ヤバいですね．
しかしこういうコードをRejectされることで，人は成長できると信じて投稿.
ええ…
流石にコレで「AC！やったね！」で終わるのはヤバすぎる．
もうちょっとがんばりましょう．
from sys import stdin
import math
input=stdin.readline
def isPrime(x):
if x % 2 == 0:
return False
for div in range(3, math.floor(x **(0.5)) + 1,2):
if x % div == 0:
return False
return True
X = int(input())
if X == 2:
print(2)
exit()
if X % 2 == 0:
X+=1
if isPrime(X):
print(X)
exit()
while (True):
X += 2
if isPrime(X):
print(X)
exit()
- 素数判定時，偶数で割らない
- そもそも偶数を素数判定しない
など．ちょっと改良しました．
誤差ですね．
そこそこ時間を描けてこねくり回したプログラムが，テキトーに実装した頭悪いソースコードと大差ないタイムで通過したのを見て，「競技プログラミングに求められる技術とはなんだろう」という気持ちになります，
下手に頭をこねくり回して数学を使ったりしてみるよりは，網羅性があって実装がラクな手段を取るべきなのでしょうか．
そのへんは戦略なのかな…
計測を忘れてましたが，多分15minほど．
#ABC149 Snack
AでもBでも割り切れる最小の値ということは，最小公倍数ですね．
AとBの最小公倍数は$A\times B \div (AとBの最大公約数)$で求められます．
AとBの最大公約数を求める問題に帰着できました．
筆者は大学生なので，ユークリッド互除法が使えることを知っています．
from sys import stdin
input=stdin.readline
#ユークリッド互除法
def gcd(a, b):
dekai = max(a, b)
tiisai = min(a, b)
div = dekai % tiisai
next_dived=tiisai
#次割られるのは，さっき割り込んできたやつ
#次割るのは，さっきの計算で出た余り
while (div != 0):
tmp=div
div = next_dived % div
next_dived=tmp
return next_dived
A,B=map(int,input().split())
#print(gcd(A,B))
print (A*B//gcd(A,B))
終わりですね．ユークリッド互除法の実装で頭がグルグルしましたが，それ以外は問題なし．
21min.
できることをやっただけなのであんまり学びがないですね．
##総括
目標としている競技プログラミングの先輩が，ABCの一桁番台までしっかりC問題埋めしているのに対し，自分はまだ150番あたりにいるので
1日10問解いても，2週間ぐらいかからないと追いつかない...
自分を鍛え直す意味でチャレンジしてみても良いかもですね．
というわけで今日はとりあえずあと8問くらい解きます．