목록소수개수 (1)

포시코딩

소수 찾기, 소수의 개수 구하기

처음엔 나도 다른 사람들처럼 for문 두개로 2부터 n까지 모든 수로 나눠보며 소수를 찾는 방법으로 풀이했는데 정확도만 측정하는 테스트에서조차 시간초과나는 테스트케이스가 있었다. 솔직히 이런 소수를 다뤄본적이 많이 없었기 때문에 해당 문제의 질문답변 항목을 보던중에 엄상우 라는 분의 https://school.programmers.co.kr/questions/21359 글에서 정수론 관련하여 소수의 대한 성질을 이용해 연산 과정을 급격하게 줄이는 방법을 알게됨 해당 글의 3번은 앞의 1, 2번에서 다 해결되므로 알고만 있는거로 하고 (소수인지 여부를 묻는데 짝수면 1, 2번의 과정 없이도 바로 판별이 가능하므로) n은 2이상 1000000이하의 자연수고 n이 소수인지의 여부를 묻는게 아닌 그 사이에 소수..
자료구조알고리즘/문제풀이 2022. 11. 22. 23:07
이전 Prev 1 Next 다음