delpho

문제 링크 성능 요약 메모리: 229620 KB, 시간: 4100 ms 분류 수학(math), 정수론(number_theory), 소수 판정(primality_test), 에라토스테네스의 체(sieve) 문제 설명 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아니다. 골드바흐의 추측은 유명한 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 이러한 수를 골드바흐 수라고 한다. 또, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다. 예를 들면, 4 = 2 + 2, 6 = 3 +..

문제 링크 성능 요약 메모리: 26404 KB, 시간: 192 ms 분류 수학(math), 정수론(number_theory), 소수 판정(primality_test), 에라토스테네스의 체(sieve) 문제 설명 M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. 출력 한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다. 문제 풀이 리뷰 주어진 조건을 보니 이중 for문으로 돌면 시간 초과가 뜰거같았다 그래서 시간복잡도를 최대한 줄이기 위해, 제곱근까지의 범위로 소수를 구했지만 답이 계속 틀렸다 (이유는 모름) import java...