Altiora Petamus

1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 🤔생각해보기 문제는 간단하다. 에라토스테네스의 체를 사용해서 풀면 된다. 개인적으로 소수 구하는 문제에서 자주 쓰는 방법은 제곱근까지만 약수의 여부를 검증해서 O(logN)의 시간 복잡도로 구하는 것이다. 에라토스테네스의 체는 다량의 소수를 한 번에 판별할 때 쓰면 좋은 방식으로 자세한 내용은 다음을 참고하자. 위키독스 온라인 책을 제작 공유하는 플랫폼 서비스 wikidocs.net m, n = map(int, input().split()) a = [False, False] + [True] *..

4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 문제 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다. 예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23) 자연수 n이 주어졌을 때, n보다 크고,..

2581번: 소수 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. www.acmicpc.net 🤔생각해보기 소수를 찾는 것은 여러가지 방법이 있지만, 평소 애용하는 방법은 제곱근을 통해서 구하는 방법이다. math.sqrt() 의 효율성에 대해 여러 의견이 있긴하던데, 아직까지 느려서 실패한 적은 없는 것 같다. 로직은 다음과 같이 처리하면 된다. 소수인지 검사해서 배열 prime에 담는다. prime이 비어있다면, -1 을 출력하고 값이 있다면 합과 최소값을 각각 출력한다. 성공 코드 # 소수 # 기본수학 2 # 소수를 찾아서 리스트에 넣기 # 배열에서 최소값 m..