[백준] 소수 구하기 1929번

[ 소수 구하기 문제 ] - 백준 1929번 소수 구하기는 코딩 테스트에서 가장 기본 중에 해당하는 문제입니다. 소수는 1과 자기 자신만으로 나누어 떨어지는 숫자를 의미합니다. 4는 소수 일까요?

4의 약수는 1, 2, 4로 총 3개 입니다. 7은 소수 일까요? 7의 약수는 1, 7로 총 2개 입니다.

특정 숫자가 소수인지 아닌지를 판별하기 위해서는 2부터 N까지의 숫자를 나누어 나머지가 0인지 확인해야 합니다. 과거에는 이중 for문을 돌려서 각각의 정수를 1부터 정수까지 다시 나누어서 떨어지는 카운팅 값이 2개일 경우 소수로 반환하는식으로 문제를 풀었습니다.

이를 시간 복잡도로 나타내면 O(n2) 으로 쉽게 말해서 좋지 않은 성능을 보이는 것을 확..........