Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
29 | 30 | 31 |
Tags
- 에라토스테네스의 체
- 백준
- 시뮬레이션
- 완전탐색
- JUnit 5
- 문자열
- 스택
- 백트래킹
- 알고리즘
- 그리디
- 투 포인터
- 동적계획법
- 프로그래머스
- 플로이드-와샬
- 세그먼트 트리
- dfs
- Effective Java
- java
- BFS
- 수학
- 구현
- swea
- mst
- 이분탐색
- Network
- 후니의 쉽게 쓴 시스코 네트워킹
- CS
- 위상정렬
- 유니온 파인드
- Kotlin
Archives
반갑습니다!
[알고리즘] 에라토스테네스의 체 본문
소수 찾기 문제를 풀고 기왕 포스트하는김에 이론정리를 해놓는게 낫겠다는 생각이 들어서 정리하였다.
소수를 찾는 알고리즘이다.
위의 동영상처럼 1부터 N까지 숫자를 순회하며 순회한 수들의 배수를 제거하는 방법이다.
구체적인 구현 방법은 코드를 살펴보자
n을 입력받아서 1~n까지의 숫자 중에서 소수인 숫자를 출력하는 코드이다.
#include <vector>
#include <iostream>
using namespace std;
void precalc(vector<bool>& prime, int n){
prime[1] = false;
for(int i=2; i*i<=n; i++){
if(prime[i] == true)
for(int j=i*i; j<=n; j+=i){
if(prime[j] == true) prime[j] = false;
}
}
}
int main(){
int n;
cin >> n;
vector<bool> prime(n+1, true);
precalc(prime, n);
for(int i=1; i<=n; i++){
if(prime[i] == true)
cout << i << ' ' << 는 소수입니다 << endl;
}
return 0;
}
'CS' 카테고리의 다른 글
[Network] URL, URN, URI (0) | 2020.05.12 |
---|---|
[Network] 쿠키와 세션 (0) | 2020.05.12 |
[Network] TCP와 UDP (0) | 2020.05.05 |
[Network] GET과 POST (0) | 2020.05.05 |
[알고리즘] 투 포인터 (0) | 2020.04.17 |