백준 1929번

(C++) 백준 1929번 - 소수 구하기

문제 링크 : https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 문제 풀이 에라토스테네스의 체를 사용한 풀이이다. #include #include using namespace std; int m, n; vector state(1000005, true); void prime(int n){ state[1] = false; for(int i = 2; i*i m >> n; prime(n); for(int i = m; i

(Python) 백준 1929번 - 소수 구하기

문제 링크 : https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 풀이 저번에 풀이했던 1978번과 같은 방식인 에라토스테네스의 체로 풀이를 했다. 다만 2부터 (자기 자신 - 1)을 모두 나눠보면 시간 초과가 발생하여 어떻게 해야 하는지 고민하던 중, 2부터 √자기자신 까지만 나눠도 된다는 사실을 알게 되어 그렇게 풀이해 보니 제한 시간 내에 통과할 수 있었다. import sys import math n, m = map(int, sys.stdin.readline().split..