문제 URL : www.acmicpc.net/problem/1929
1929번: 소수 구하기
첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.
www.acmicpc.net
문제 접근법 : 여러가지 소수를 가장 빠르게 구하기위한 알고리즘인
에라토스테네스의 체를 이용하면 쉽게 구할수있습니다.
에라토스 체를 이용하여 주어진 최대값까지 소수를 구한후
해당 범위내에 있는 소수를 출력하면 됩니다.
소스코드:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
//By 콩순이냉장고
#include <iostream>
using namespace std;
int n, m;
int p[1000001] = {1,1};
void erathos(){
for (int i = 2; i*i <= m; i++){
if (p[i] == 0){
for (int j = i + i; j <= m; j += i){
p[j] = true;
}
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
erathos();
for (int i = n; i <= m; i++)
{
if (p[i] == false)
cout << i << "\n";
}
}
|
cs |
궁금한점 혹은 모르는점 혹은 논리적인 오류등
어떤 질문이 있다면 언제든지 댓글은 환영입니다.
'백준' 카테고리의 다른 글
| 백준 3190 뱀 (0) | 2021.02.10 |
|---|---|
| 백준 1525 퍼즐 (0) | 2021.01.01 |
| 백준 16938 캠프 준비 (0) | 2020.12.31 |
| 백준 9944 NxM 보드 완주하기 (0) | 2020.12.31 |
| 백준 12931 두 배 더하기 (0) | 2020.12.31 |
