백준 1644: 소수의 연속합 (Swift)

꽤나 까다로운 문제였다..

일단 문제를 읽어보면, 해당 숫자 이하의 모든 소수(prime number)를 배열에 오름차순으로 모아놓고,

투포인터로 연속된 소수 합이 주어진 숫자 n이 되는 경우를 모두 세주면 된다.

 

소수 배열을 만드는 것은 "에라토스테네스의 체" 알고리즘을 사용하였는데,

보통 어떤 자연수 n이 prime인지 판별하기 위해서는,  루트n이하의 소수들에 대해서, n을 나누어 떨어지게 할 수 있는지 체크하면된다.

 

이 경우에는 루트 n이하의 소수들만 배열에 넣어버리면, 연속합을 체크할 수 없다.

ex) 23의 경우, 2 3 5 7 11 13 17 19 23의 소수 순열 중,

루트23, 즉 4.~~ 아래의  [ 2, 3 ]만 배열에 넣으면 연속합이 23이 되는 것을 체크할 수 없다.

 

또한, 주어진 숫자 n자체가 소수(prime)인지 아닌지도 판별을 해서 count해줘야하기 때문에,

숫자 N을 입력받으면, n번 인덱스까지 가지는 배열을 만들어 자연수 1~ n에 대하여 소수여부를 저장하였다.

 

 

# Swift point:

stride의 경우, to:~에 입력하는 숫자는 포함을 시키지 않으므로,, n까지 포함시키기 위해 to: n+1과 같이 작성하였다.!!