Programmers/프로그래머스-소수 찾기-python

📖 문제

🎈 풀이

• 첫번째 반복문에서는 1부터 n까지 돌며 소수인지 판별할 수를 만들고 판별할 flag와 i은 무시처리했다.
• 두번째 반복문에서 판별할 수를 나눌 수를 만들 j를 만들었고, 한번이라도 나눠떨어지면 flag는 1이 되어 소수가 아니므로 answer에 수를 더해주지 않는다.
• 이 때 2부터 i-1까지 계속 나눠주지 않고 i의 제곱근까지만 보면 된다는 것을 활용해서 연산의 개수를 낮출 수 있었다.
  (모든 약수가 가운데 약수를 기준으로 곱셉 연산에 대한 대칭을 이루는 것을 이용)
• 소수의 개수의 합인 answer를 return해준다.
  

💻 코드

💊 탑👍 코드

• 정확히는 모르겠지만 "에라토스테네스의 체"를 사용한 것이라고 한다.
• 소수판별할 때 많이 쓰이는 알고리즘 같다.
• 이후 추가적으로 공부해보려 한다.
• 여기에 위의 대칭을 이용한 연산을 줄이는 것을 활용하면 더 복잡도를 낮출 수 있다고 한다.

✨ 실행 결과

💡 문제 출처

프로그래머스