문제 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 풀이 입력받은 자릿수의 모든 수를 차례대로 소수 판정하는 것은 시간이 오래걸린다. 대신, 신기한 소수는 왼쪽의 한 자리 수부터 소수여야 한다는 점을 이용하여 경우의 수를 줄일 수 있다. 백트래킹을 이용해 현재 소수인 수들만 다음 자리수를 더한 소수를 찾는 탐색을 진행하면된다. 먼저 신기한 소수가 되려면 첫째 자리 수가 소수인 2, 3, 5, 7 중 하나여야 한다. 그 외의 수로 시작하는 수는 다음 단계로 진행하지 않는다. 예를 들어 첫째 자리가 ..

문제 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의 배..