Codility - CountSemiprimes 문제풀이 - Henry's Algorithm

 

아래는 생각나는대로 에라토스테네스의 체를 사용하여 문제를 풀려고 했던 방법이다.

하지만 생각대로 쉽게 풀리지 않았다.

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(N, P, Q):
    # write your code in Python 3.6
    
    result = []
    for a,b in zip(P,Q):
        
        if b <= N:
            c = b
        else:
            c = N
        result.append(len(get_prime(N,a,c)))
    
    #print(result)
    return result
    pass

def get_prime(num,a,b):
    arr = []
    if num <= 1:
        return arr
    arr2 = []
    
    for i in range(2,num+1):
        flag = True
        for j in range(len(arr)):
            if i%arr[j] == 0:
                flag = False
                break
        if flag:
            if a <= i**2 and i**2 <= b:
                arr2.append(i*i)
            arr2.extend([k*i for k in arr if a <= k*i and k*i <= b])
            arr.append(i)
    return arr2
        

 

 

 

구글링을 통해서 해답을 알게 되었다.

해답은 인덱스를 사용하여 계산을 하는 것이다.

 

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

import math

def solution(N, P, Q):
    # write your code in Python 3.6
    # N+1의 개수를 가진 빈 배열을 만들어준다.
    arr = [0]*(N+1)
    semi_cnt = [0]*(N+1)
    each_sum = 0

    #1~N 까지의 범위의 수를 소수와 소수의 배수로 구분함
    i = 2
    while i <= math.sqrt(N):
        if arr[i] == 0:
            j = i*i
            while j <= N:
                arr[j] = i
                j += i
        i += 1
    #print(arr)

    # 인덱스를 통해서 문제를 풀어준다.(소수일때, 나누고 나눈 값이 다시 소수라면 +1)
    for i in range(1,N+1):
        if arr[i] != 0:
            j = i//arr[i]
            if arr[j] == 0:
                each_sum += 1
        semi_cnt[i] = each_sum

    #rint(semi_cnt)

    result = []

    # 범위에 따라 소수의 개수를 차감하여 값을 배열에 넣어준다.
    for i,j in zip(P,Q):
        result.append(semi_cnt[j]-semi_cnt[i-1])

    #print(result)
    return result

    pass