PythonでLINEの新卒コーディングテストの問題を解いてみたメモ

コーディングテストのアルゴリズム問題
https://engineering.linecorp.com/ja/blog/algorithm-description-for-coding-tests/
この記事はpython2系で書かれているらしいのでpython3系で書き直してみて自分が理解できるようにまとめてみました。
今までエラー処理を全然書いてこなかったので、今回は書いてみました。うまくいっている自信がないのですが…

問題

N番目の素数を探せ

1から昇順で数えたときに、N番目にあたる素数を出力するコマンドラインツールを作成してください。
入力：出力したい素数の番号　N
出力：N番目の素数

入力例１：5
出力例１：11

考え方

素数を求めるのでエラトステネスの篩を用いる。
まず、一番小さな素数である2をdata配列に入れる。
そして、data配列に見つけた素数をどんどん入れていき、N個の素数を見つけたらwhileループから脱出し、その時の最後の素数を出力するようにする。
素数を見つける際に、それまでに見つけた素数が入ったdata配列を用いる。

解答例1

sieve_of_eratosthenes.py

n = int(input())

def get_prime_by_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError("n is int-type.")
    if n < 1:
        raise ValueError("n is more than 1.")
    data = [2]
    num = data[0]
    while len(data) < n:
        isPrime = True
        num += 1
        for d in data:
            if num % d == 0:
                isPrime = False
                break
        if isPrime:# numが素数ならば
            data.append(num)
    return data[n-1]

def main():
    print(get_prime_by_sieve_of_eratosthenes(n))
    
if __name__ == "__main__":
    main()

これでも正しく動作するが、素数かどうかを判定する処理であるisPrimeを独立させ、関数化するとすっきりとさせることができそう。
また、リスト内包表記でもうまくいくかも？そっちの方がきれいかな？

解答例2

解答例1のisPrimeフラッグを関数化してみた。

sieve_of_etatoshtenes2.py

n = int(input())

def is_prime(num,data):
    for d in data:
        if num % d == 0:
            return False
    return True

def get_prime_by_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError("n is int-type.")
    if n < 1:
        raise ValueError("n is more than 1.")
    data = [2]
    num = data[0]
    while len(data) < n:
        num += 1
        if is_prime(num,data):
            data.append(num)
    return data[n-1]

def main():
    print(get_prime_by_sieve_of_eratosthenes(n))
    
if __name__ == "__main__":
    main()

for文の多重ループを抜け出す際にはそれらをまとめて関数化するとすっきりとすることが分かった。

参考

Wikipedia

[Pythonで作るエラトステネスのふるい]
(https://qiita.com/fantm21/items/5e270dce9f4f1d963c1e)

感想

久しぶり過ぎでQiitaの使い方から見直した。そして問題が解けてうまくいったときはやっぱり楽しいものだと思った。