N을 입력받으면 반복문을 루트N만큼 반복해서
1부터N까지 소수를 전부 출력하는걸 짜라는데
N이 100이라 치면 출력하는데만 반복문 24번 돌고
출력하는거 제외한다 쳐도
에라테스토너스 써도 무조건 반복문이 10번 무조건
넘겨버리는데
여기서 이진탐색 개념을 어떻게 적용시킬수 있을까?
1부터N까지 소수를 전부 출력하는걸 짜라는데
N이 100이라 치면 출력하는데만 반복문 24번 돌고
출력하는거 제외한다 쳐도
에라테스토너스 써도 무조건 반복문이 10번 무조건
넘겨버리는데
여기서 이진탐색 개념을 어떻게 적용시킬수 있을까?
9개의 댓글
무분별한 사용은 차단될 수 있습니다.
decltype
아니 필즈상이 아니라 수학 교과서에 영원히 이름이 실릴듯
ᅟᅟᅟᅟ ㅤㅤㅤ
decltype
알파스트라이크
C가 합성수면 C = A * B (A, B는 1보다 큰 자연수). 따라서 둘 중 하나는 루트C보다 작거나 같음.
따라서 모든 수 검증할 필요 없이 루트 C이내로만 나눠봐서 검증하면 됨.
즉 내부 하나의 수에 대해 검증하는 루프는 따로 있고 그 루프를 돌리는걸 루트C번 까지 하란 문제 같은데. 즉 이중루프 구조에서 외부 루프를 루트C 만큼만.
참고로 소수 알고리즘 다룰 때 에라토스테네스의 체 이야기하면서 항상 같이 나오는 거니 검색해보면 아마 같이 나올거임.
decltype
그게 가능하면 소수테스트 하는 루프 시간복잡도 루트N*외부 루프 루트N해서 O(N)안에 N이하의 소수를 판별하는 알고리즘이 완성되는데, 현존하는 어떤 알고리즘보다 빠름...
알파스트라이크
decltype
여기서 내부 루프를 외부 루프로 잘못쓴거지?
내부루프가 primality test하는 루프아녀?
알파스트라이크
여튼 결론은
2부터 N-1까지 소수 구할 때 당연히 에라토스테네스의 체를 쓰잖아? 그 체를 쓰는 방식 자체가 2배수 모두 거르고 3배수 모두 거르고... 루트N까지 거르고 끝임. (루트N)+1부터는 이미 '걸러진 상태'기 때문에.
애초 저 문제 낸 양반이 알고리즘 쪽 강의하는 교수나 이런 사람이라면 이거 의도한거였을게 100퍼임.
decltype