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