문제 1747번: 소수&팰린드롬 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, www.acmicpc.net 풀이 먼저 에라토스테네스의 체를 이용해 소수 판정을 하고, whlie문을 이용해 입력받은 수보다 큰 팰린드롬 수를 찾으면 된다. 에라토스테네스의 체는 소수의 배수들을 지워가면서 소수를 판정하는 것으로 다음 이미지를 보면 쉽게 이해할 수 있다. 문제에서 주어진 범위 1000000보다 큰 팬린드롬 소수는 1003001이기때문에 소수 판정은 1003001까지만 하면 된다. 팰린드롬의 확인은 수를 문자열로 변환하여 확인하면 된..

문제 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 풀이 에라토스테네스의 체를 활용하여 소수 판정을 먼저 수행하고, 투 포인터를 이용하여 합이 입력받은 값이 되는 경우를 세어주면 된다. 에라토스테네스의 체는 범위 내에서 소수의 배수는 모두 지워가며 소수를 구하는 방법이다. 다음의 그림을 보면 쉽게 이해할 수 있다. 먼저 입력받은 범위까지의 소수를 구하고, 그 소수를 리스트에 저장한다. 이 리스트를 시작과 끝을 가리키는 start와 end 포인터를 활용하여 탐색한다. 두 포인터는 초기에 0으로 초기화되며, 두 포인터 사이의 값의 합과 찾으려는 값을 비교하면서 탐색한다. 만약 현재까지의 누적 합이 찾으려는 값보다 작다면 end 포..

문제 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 풀이 어떤 수가 소수인지 알기 위해서 아래 코드로 판별할 수 있지만, 범위 내에 모든 수를 아래와 같은 방법으로 판별한다면 비효율적이고 이 문제에서 시간초과가 발생한다. for(i in start .. end) { var cnt = 0 for(j in 1..i) { if(i%j==0) { cnt++ } } if(cnt==2) { println(i) } } 대신 에라토스테네스의 체를 이용하여 해결할 수 있다. 에라토스테네스의 체는 범위 내에서 소수의 배수는 모두 지워가는 방식이다. 2의 배..