에라토스테네스의 체2 에라토스테네스의 체 1. 개요 1. 고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법 2. 시간 복잡도 = O(n) 2. 방법 step 1) 숫자 1 ~ 100 쓰기 step 2) 소수도, 합성수도 아닌 유일한 자연수 1을 제거 step 3) 2를 제외한 2의 배수를 제거 step 4) 3을 제외한 3의 배수를 제거 step 5) 4는 뛰어넘고, 5의 배수를 제거 step 6) 위의 방법과 동일하게 제거해나간다. 3. 소스 코드 #include constexpr int MAX=1000001; bool prime[MAX]; void eratosthenes(){ memset(prime, false, MAX);//배열을 초기화한다. prime[2]=true;//2는 소수다. prime[3]=true;//3은 소수.. 2023. 10. 3. [백준 C++] 27172번: 수 나누기 게임 1. 문제 https://www.acmicpc.net/problem/27172 27172번: 수 나누기 게임 《보드게임컵》을 준비하다 지친 은하는 보드게임컵 참가자들을 경기장에 몰아넣고 결투를 시키는 게임 《수 나누기 게임》을 만들었습니다. 《수 나누기 게임》의 규칙은 다음과 같습니다. www.acmicpc.net 2. 알고리즘 분류 수학 프루트포스 알고리즘 정수론 소수 판정 에라토스테네스의 체 3. 소스 코드 #include #include #include using namespace std; vector numbers; int scores[1000006]; int cards[1000006]; int main() { ios_base::sync_with_stdio(false); cin.tie(0); co.. 2023. 6. 10. 이전 1 다음
