개발윗미

[에라토스테네스의 체란 ?] 에라토스테네스의 체는 다수의 자연수에 대하여 소수 여부를 판별할 때 사용하는 대표적인 알고리즘이다. 에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾을 때 사용할 수 있다. 에라토스테네스의 체 알고리즘의 동작 과정은 다음과 같다. 1. 2부터 N까지의 모든 자연수를 나열한다. 2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다. 3. 남은 수 중에서 i의 배수를 모두 제거한다. (단, i는 제거하지 않는다.) 4. 더 이상 반복할 수 없을 때까지 2번과 3번의 과정을 반복한다. 이러한 에라토스테네스의 체를 이용해서 소수판별 프로그램을 C언어로 구현한 코드는 아래의 게시물에서 확인할 수 있다. https://unie2.tistory.com/42?categ..

[소수란 ?] 소수란 1보다 큰 자연수 중에서 1과 자기자신을 제외한 자연수로는 나누어 떨어지지 않는 자연수이다. 즉, 6은 1, 2, 3, 6으로 나누어 떨어지므로 소수가 아니며, 7은 1과 7을 제외한 다른 수로 나누어 떨어지지 않기 때문에 소수이다. [기본적인 소수 판별 예제] def is_prime_number(x) : for i in range(2, x) : if x % i == 0 : return False return True print(is_prime_number(4)) print(is_prime_number(7)) 소수 판별 함수(is_prime_number) 를 통해 2부터 x-1 까지의 모든 수를 확인하며 만약 x가 해당 수로 나누어 떨어지면 소수가 아니기 때문에 False를 반환하고..

에라토스테네스의 체는 소수를 찾는 방법이다. 여기서 소수는 1과 자기자신을 약수로 가지는 모든 자연수이며, 대표적으로 2, 3, 5, 7, 11, 13, ... 등이 존재한다. 우선, 에라토스테네스의 체를 사용하지 않고 기본적인 소수 판별 코드는 다음과 같다. [소수 판별 기본 코드] #include bool isPrimeNumber(int x) { for(int i=2; i