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問くらい解きます．

AtCoder C問題埋め 0610

ABC149 Next Prime

ABC149 Snack

総括