[AtCoder][競技プログラミング][Python3]ABC 250 D-250-like Number

AtCoder

Photo by Opollo Photography on Pexels.com

2022.05.12

Table of Contents

問題

D - 250-like Number

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

方針

結局素数かどうかの判定はしないといけない。素数判定は前に作った以下のcodeで。

import math
def is_prime(m):
    if m == 1:
        return False
    elif m < 4:
        return True
    elif m % 2 == 0:
        return False
    elif m < 9:
        return True
    elif m % 3 == 0:
        return False
    else:
        r = math.floor(math.sqrt(m))
        f = 5
        while f <= r:
            if m % f == 0:
                return False
                break
            elif m % (f+2) == 0:
                return False
                break
            f += 6
        return True

ここからだが、\(N \geq pq^3 \geq p^4\)なので、\(4\)乗して\(N\)を超えない素数までのリストを作っておけば良い。甘めに\(\sqrt[3]{N}\)までの中から素数をリストアップする。

素数のリストを作って、\(pq^3\)が\(N\)を超えないか判定していく。

解答

#atcoder template
def main():
    import sys
    input = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    n = int(input())

    #output
    #n >= pq^3 > p^4
    upper_lim = int(pow(n, 1/3)) + 1

    import math
    def is_prime(m):
        if m == 1:
            return False
        elif m < 4:
            return True
        elif m % 2 == 0:
            return False
        elif m < 9:
            return True
        elif m % 3 == 0:
            return False
        else:
            r = math.floor(math.sqrt(m))
            f = 5
            while f <= r:
                if m % f == 0:
                    return False
                    break
                elif m % (f+2) == 0:
                    return False
                    break
                f += 6
            return True

    prime_list = []
    for i in range(1, upper_lim):
        if is_prime(i):
            prime_list.append(i)

    answer = 0
    l = len(prime_list)
    for i in range(l):
        for j in range(i+1, l):
            if prime_list[i]*prime_list[j]**3 <= n:
                answer += 1
            else:
                break

    print(answer)

    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()