백준 2581번 문제풀이 - 소수

백준 2581번 문제풀이 - 소수

백준 2581번 문제

https://www.acmicpc.net/problem/2581

M이상 N이하의 모든 자연수의 소수를 판별하는 문제이다. 바로 전의 소수문제보다 많은 수를 처리해야 된다

이 문제는 나만의 방법으로 풀고 소수 문제를 공부하면서 배운 에라토스테네스의 체도 사용해보았다.

코딩

1.

N-M+1개의 배열을 만들어서 M~N까지의 수만 소수를 확인하고 총합과 최솟값을 출력하도록 했다.

M~N까지의 모든 수를 확인해야되기 때문에 아래의 에라토스테네스의 체라는 알고리즘을 쓰는 것보다 시간 복잡도가 올라간다.

2.

에라토스테네스의 체를 이용하여 소수가 아닌 것들의 곱들까지 체크하고 이미 체크된 배열은 넘어가게 되서 시간 복잡도가 줄어든다.

결과

1.

2.

예상대로 2번째 출력 결과가 메모리나 시간면에서 더 앞서는 것을 볼 수 있다.

느낀 점

소수를 구하는 방법으로 에라토스테네스의 체라는 방법이 있다는 것을 알게 되었고 소수를 구하는 방법은 많은 수를 대입해볼 수 밖에 없다는 것이 흥미로웠다. 에라토스테네스의 체 알고리즘으로 시간복잡도를 줄이면서 같은 과정을 반복하지 않도록 알고리즘을 만드는 방식이 앞으로 알고리즘 문제를 풀 때 도움을 줄 것 같다.

참고 : https://st-lab.tistory.com/83

from http://chobojonghyun.tistory.com/15 by ccl(A) rewrite - 2021-11-15 19:27:59