에라토스테네스의 체1 프로그래머스 Lv1 소수찾기(python) 소수찾기 알고리즘 문제풀이를 안 했더니 감을 잃어서 다시 풀면서 실력을 쌓고 있다. 소수와 관련한 문제가 자주 나와서 좀 더 빠르게 소수여부를 확인할 수 없을까 하다가 에라토스테네스의 체를 알게 되었고, 잘 이용하고 있다. 우선 0과 1은 소수가 아니므로 제외하고 2 ~ n이라는 숫자가 있을 때, n까지의 숫자 중 소수가 무엇인지 확인할 때 사용하면 된다. 알다시피 소수는 1과 자기 자신으로만 나눴을 때 나머지가 0인 수를 말한다. 보통이라면 2~n까지의 숫자 i를 모두 돌면서 확인할 텐데 i를 2~(i-1)까지 또는 2~(((i-1)//2)) 까지 돌리면서 i % 해당값 == 0 이면 소수 아님의 방식으로 할 수 있다. 그러나 이 경우 모든 수를 다 확인하게 되므로 시간적으로 비효율적이다. 따라서 처음.. 2024. 1. 29. 이전 1 다음
