에라토스테네스1 에라토스테네스의 체 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. 이전 1 다음
