[Codility] 11.2 CountSemiprimes

CountSemiprimes

semiprime(반소수)는 두 소수의 곱으로 이루어진 수이다.
구간 [P[k], Q[k]]에 존재하는 semiprime의 개수를 반환한다

$N \leq 50,000$이므로 prime의 개수는 (직접 구해본 결과) 5133개이다. 따라서 semiprime을 구할 때 $O(n^2)$으로 구할 수 있다

문제 접근방법은 다음과 같다

prime을 구한 후, semiprime을 구한다
semiprime의 개수를 구하는 query를 $O(1)$로 해결 -> 누적합!

def solution(N, P, Q):
    # N이하의 수 중에서 prime 판별하기
    isPrime = [True] * (N + 1)
    isPrime[0] = isPrime[1] = False
    prime = []
    for i in range(2, N + 1):
        if isPrime[i]:
            prime.append(i)
            for j in range(i * i, N + 1, i):
                isPrime[j] = False

    # prime을 이용하여 semiprime구하기
    # semiprime[x] : x이하의 수에 semiprime의 개수
    semiprime = [0] * (N + 1)
    for p1 in prime:
        for p2 in prime:
            # 어차피 주어지는 query는 N을 넘지 않는다
            if p1 * p2 > N:
                break
            semiprime[p1 * p2] = 1
    
    # semiprime[x] : x이하의 수에 semiprime의 개수
    for i in range(1, len(semiprime)):
        semiprime[i] += semiprime[i - 1]

    ret = []
    for i in range(len(P)):
        p = P[i]; q = Q[i]
        ret.append(semiprime[q] - semiprime[p - 1])
    return ret