[백준/Python] 2023. 신기한 소수

2023. 신기한 소수 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 백트래킹 처음에는 에라토스테네스의 체를 사용하는 문제일 것이라고 생각했다. 가능한 수의 범위가 컸기 때문이다. (10**8) 하지만 사용 가능한 메모리가 4MB 뿐이라서, 가능한 범위만큼의 배열을 선언할 수는 없는 문제였다. 순차 탐색을 통해 소수를 판별하는 가장 빠른 방법 소수란, 1과 자기 자신 이외의 약수를 갖지 않는 수를 말한다. 약수의 개수를 구하는 것이 아니라, 단순 소수를 판별하는 경우에는 자기 제곱근(내림) 까지만..