백준 1644- 소수의 연속합(PYTHON)

https://www.acmicpc.net/problem/1644

[1644번: 소수의 연속합

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000)

www.acmicpc.net](https://www.acmicpc.net/problem/1644)

문제의 이해는 굉장히 쉬운 편이였다. 그냥 하나이상의 연속된 소수의 합으로 해당하는 값을 만들수 있는가?

그리고 만들수 있다면 몇가지 경우가 나오는가였다.

1. 주어진 값 이하에서 나오는 모든 소수들을 리스트로 만든다.

2. 해당하는 소수들을 처음부터 더해주면서 만약 합이 주어진값과 같으면 count해주고 아니면 조금씩 변하게 만들어주자

라는 생각으로 시작을 하였다.

1트

a = int(input())
num = 2
primelist=[]
def is_prime_number(x):
    for i in range(2,x):
        if x% i == 0:
            return False
    return True
while True :
    if(is_prime_number(num)):
        primelist.append(num)
    num+=1
    if(num>a):
        break
low, high, cnt = 0,0,0
while True:
    if(sum(primelist[low:high])) >a:
        low+=1
    elif(sum(primelist[low:high])) == a:
        cnt += 1
        low += 1
    elif high == len(primelist):
        break
    else:
        high +=1
print(cnt)

두가지 포인터를 만들어서 만약 high포인터가 맨끝까지 가면 break를 걸어주고 끝나게 된다. low와 high의 사이 합들이 만약 a보다 크거나 같으면 low를 1증가시켜줌으로써 다음으로 가능한 경우도 구하게 해준다. 합이 같으면 count를 해준다.

하지만 1트 실패. 시간초과가 떴다.

간과한게 있었는데 이 문제의 시간제한은 2초였고 입력값의 범위는 1<= N <= 4,000,000으로 내 풀이를 보면 primelist를 구해주는 곳에서 시간복잡도 O(n²)이 나오기에 틀렸다. 시간복잡도 2초안에 끝내기 위해서는 시간복잡도가 O(nlogn)를 사용해야 한다. 그래서 소수를 구해주는 리스트를 다른 방법을 사용하기로 하엿다.

2트

여기서는 검색찬스를 이용, 처음들어보는 체를 봤는데 발음도 어렵다.... 에라토스테네스의 체이다.

간단하게 에라토스테네스 체를 정리해보면

- 소수를 판별할 만큼 배열을 할당한후 아닌것을 하나씩 지우는 것이다. 그리고 남아있는것을 출력하면 소수가 된다.
예를 들어 120까지의 소수를 구하게 되면 11의 제곱이 121이므로 11보다 작은 배수들만 지워도 충분하기에

범위를 루트쓰워준값까지만 반복을 해도 충분해서 시간복잡도가 줄어들었다. 

그 후 해당하는 배수들의 값들을 false로 바꿔주고 리턴값 리스트에는 한번밖에 안걸린 true값들을 출력해주면 소수들의 배열을 가져올수 있다. 

시간복잡도는 O(NloglogN)이 된다.

a = int(input())
num = 2
def prime_list(n):
    sieve = [True] * (n+1)
    m = int(n ** 0.5)
    for i in range(2, m+1):
        if sieve[i] == True:
            for j in range(i+i, n+1, i):
                sieve[j] = False
    return [i for i in range(2,n+1 ) if sieve[i] == True]
primelist = prime_list(a)
low, high, cnt = 0,0,0
while True:
    if(sum(primelist[low:high])) >a:
        low+=1
    elif(sum(primelist[low:high])) == a:
        cnt += 1
        low += 1
    elif high == len(primelist):
        break
    else:
        high +=1
print(cnt)