- 소수찾기(하나의 수)
소수 는
1보다 큰 자연수중에서 1과 자신을 제외한 자연수로는 나누어지지 않는 자연수를 뜻한다.
소수 찾는 알고리즘)
같이 작성한다면 임의의 값 x 가 소수인지 아닌지 알수있다.
출력 값.
하지만, 이처럼 작성한다면 시간 복잡도는 O(X)로 x의 값이 커질수록 선형적으로 커진다.
시간 복잡도를 줄이기 위해 먼저 약수에 대해 알아보자
모든 약수가 가운데 약수를 기준으로 곱셈 연산에 대해 대칭을 이룬다.
- 예를들어 16의 약수는 1, 2, 4, 8, 16 이다.
가운데 약수인 4를 기준으로 좌우대칭으로 곱하면 16이 나온다.
이때 가운데 약수는 제곱근의 값이다.
이처럼 제곱근을 이용하면 시간 복잡도를 줄일수있는데, 알고리즘은 다음과 같다.
처음 내용과 비슷하지만 math 라이브러리를 호출하여 2부터 x의 제곱근까지의 값으로 x를 나누었을때 x가 나누어 떨어지지 않는다면 소수라는것을 출력 값으로 알수있다.
for문의 범위 값 이 2부터 x-1까지 보다 x의 제곱근 값이 적기때문에
기존의 알고리즘보다 시간복잡도 면에서 더 좋다는 것을 알수있다.
- 다수의 소수 찾기 (범위 안에 존재하는 모든 소수)
다수의 자연수에 대하여 소수를 판별할때는 에라토스테네스의 체 알고리즘을 사용한다. 에라토스테네스의 체 의 구체적인 동작 과정은
- 1) 2 부터 n까지의 모든 자연수를 나열한다.
2) 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다.
(이때 i의 값은 소수)
3) 남은 수 중에서 i의 배수를 제거(i는 소수기 때문에 제거x)
4) 더 이상 반복할 수 없을 때까지 2~3 번 반복.
에라토스테네스의 체를 이용한 알고리즘 이다.
제곱근을 이용하기 위해 math 라이브러리를 호출하고
범위 n까지의 소수를 찾기위해 n 의 입력 값 과
소수를 출력하기위해 True(소수)로 초기화
2부터 n제곱근까지 방문하며 초기의 i값은 소수로 설정
i의 배수를 제외 하기 위한 j 값 설정
ij 값이 n 이하 값을 가질때까지 반복
i j 값은 False (소수가 아님)
j를 1씩 더하며 배수들을 확인
for 문으로 범위값 설정하여 출력 하면
26을 입력하였을때 아래의 출력 값 을 구할 수 있다.
:)