Coding Test - cpp
[C++] 소수 구하기 (에라토스테네스의 체)
에드윈H
2020. 11. 26. 21:35
1929번: 소수 구하기
첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.
www.acmicpc.net
위 문제를 풀어보다가
[C++] 소수 구하기 (에라토스테네스의 체)
보통 소수라 하면, 1과 자기자신을 제외하고는 나누어 떨어지지 않는 수라고 불린다. 이를 구하기 위해서 하나 하나씩 나누어 떨어지는 지 검사를 하고는 했는데 더 빠르게 구할 수 있는 방법이
redcoder.tistory.com
를 참고했다.
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
int m=0, n=0;
cin >> m >> n;
bool * arr = new bool[n]; //최대 범위크기만큼 동적배열 지정 (단점 메모리 낭비)
for (int i = 2; i <= n; i++) //모든 배열 true
arr[i] = true;
for (int i = 2; i * i <= n; i++)
{
if (arr[i] == false) { //이미 소수가 안되는 수 판별 false
continue; //18줄 for문으로
}
if (arr[i] == true){
for (int j = i * i; j <= n; j += i)
arr[j] = false;
}
}
for (int i = m; i <= n; i++) { //정한 범위내에서만
if (arr[i]) //소수인수 출력
cout << i << "\n";
}
return 0;
}