[백준 파이썬] 에라토스테네스의 체

에라토스테네스의 체

 

스터디를 통해 이해했던 내용을 바탕으로 정리해보았다.

 

수학적으로 정확하게 풀어냈다기 보단 스스로 이해한 바를 정리한 것으로 참고만 하길 바란다.

 

합성수 여부 판단

에라스토테네스의 체를 통해 소수와 합성수 여부를 판단할 수 있다.

 

​ ※ '소수 2개의 곱를 이용해서 합성수를 만들 수 있다' 는 가정에서 시작한다.

 

​ N = 6일 때(N>1), 6은 합성수에 해당한다.

​ 합성수는 2개의 숫자 곱으로 표현할 수 있다. 이때 작은 수를 K, 큰 수를 L로 둔다. ex) 6 = 2 * 3

$$ 1<N=KL $$

 

​ K**2 보다 KL이 크다는 성질이 있다. ex) 2*2 = 4 <= 6

$$ 1<KK<=KL=N $$

 

​ K로 N을 표현하면 다음과 같게 된다. ex) 2 <= 6**0.5

$$ 1<K<=N**0.5 $$

 

​ 'N이 합성수일 때 위 식이 해당한다'는 가정이 성립된다.

만약 위 가정이 성립되지 않는다면, 가정이 잘못된 것이므로, 'N은 합성수가 아니다 = 소수일 것이다'는 추론이 가능하다

 

결론

합성수 여부를 판단할 때 2부터 N까지 나눗셈을 진행하며 모든가능성을 검토할 필요가 없다.

 

2부터 N**0.5 범위까지만 확인해보면 합성수인지, 소수인 지를 파악할 수 있다.

 

컴퓨터 계산과정을 간소화하여 시간초과 문제를 해결할 수 있다.

 

관련된 백준 문항

소수 관련 문항 예시

# 2581 소수(실버 I)

# 9020 골드바흐 추측(실버 I)