[Codility/Lesson11]CountSemiPrimes

| 1트

def solution(N, P, Q):

    sieve = [1 for _ in range(N + 1)]
    sieve[0]=sieve[1] = 0

    i = 0 
    while i * i <= N:
        if sieve[i]:
            k = i * i
            while k <= N:
                sieve[k] = 0 
                k += i
        i+= 1

    prime = []

    for i, is_prime in enumerate(sieve):
        if is_prime:
            prime.append(i)
    
    #print(prime)

    semi_prime = [0 for _ in range(N + 1)]

    for num in prime:
        for next_num in prime:
            if num * next_num > N:
                break 
            else:
                #print(num * next_num)
                semi_prime[num * next_num] = 1 
    #print(semi_prime)

    answer = []

    for (start, end) in zip(P, Q):
        count = 0 
        for idx in range(start, end + 1):
            if semi_prime[idx]:
                count += 1 
        answer.append(count)
    
    #print(answer)
    return answer 

• 일단 아무 생각 없이 소수 구하고 -> 소수 * 소수로 semi_prime 구하고 -> 갯수 세기를 했다
• 엄청 오래걸릴 줄 알았는데 생각보다 오래 안걸렸다
• 하지만 몇몇개 time out이 걸렸다

결과는 여기에

| 2트

def solution(N, P, Q):

    sieve = [1 for _ in range(N + 1)]
    sieve[0]=sieve[1] = 0

    i = 0 
    while i * i <= N:
        if sieve[i]:
            k = i * i
            while k <= N:
                sieve[k] = 0 
                k += i
        i+= 1

    prime = []

    for i, is_prime in enumerate(sieve):
        if is_prime:
            prime.append(i)
    
    #print(prime)

    semi_prime = [0 for _ in range(N + 1)]

    for num in prime:
        for next_num in prime:
            if num * next_num > N:
                break 
            else:
                #print(num * next_num)
                semi_prime[num * next_num] = 1 
    #print(semi_prime)

    answer = []

    semi_count = 0 
    semi_prime_count = [0 for _ in range(N + 1)]

    for i, num in enumerate(semi_prime):
        if num:
            semi_count += 1 
        semi_prime_count[i] = semi_count
    
    #print(semi_prime_count)
    for (start, end) in zip(P, Q):
        answer.append(semi_prime_count[end] - semi_prime_count[start - 1])
    
    #print(answer)
    return answer 

• 해당 index까지 semi_prime이 몇번 등장했나 그때그때 세는게 아니라 미리 처음부터 N+1까지 세어놓고 사용하기로 했다
• 그래서 timeout이 걸리지 않게 되었다

결과는 여기에