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
- mst
- java
- 문자열
- 완전탐색
- 구현
- 에라토스테네스의 체
- BFS
- 동적계획법
- 스택
- 백준
- Effective Java
- 플로이드-와샬
- swea
- 유니온 파인드
- dfs
- 수학
- CS
- JUnit 5
- 알고리즘
- 후니의 쉽게 쓴 시스코 네트워킹
- 이분탐색
- 위상정렬
- 백트래킹
- 그리디
- 투 포인터
- 프로그래머스
- Kotlin
- Network
- 세그먼트 트리
- 시뮬레이션
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 |