728x90 에라토스테네스의 체1 [알고리즘] 에라토스테네스의 체(c++)구현 및 문제풀이 - 코딩기록 에라토스테네스의 체는 소수를 찾는 방법 중 하나로 범위 안에 있는 소수들을 모두 구해야 할 때 유용하게 사용되는 알고리즘이다. 원리 소수는 1과 자기 자신만을 약수로 가지는 수이기 때문에 약수의 개수가 2개이고 합성수는 소수가 아닌 수를 말하기 때문에 약수의 개수가 2개보다 많다. 이 사실을 통해 소수에 어떤 수를(1 제외) 곱하게 되면 그 수는 반드시 합성수가 된다는 것을 알 수 있다. 이것이 에라토스테네스의 체 알고리즘의 핵심 아이디어이다. 코드 일단 우리의 목표는 2부터 100까지에 해당하는 모든 소수를 구하는 것이다. 우리가 처음 만나는 수를 2라고 가정해보자. 그렇다면 소수인 2에 어떤 수를 곱하면 그것은 합성수일 것이다. 즉, 4, 6, 8, ... 50, ..., 100(2에 어떤 수를 곱한.. 2023. 5. 2. 이전 1 다음 728x90
