소수

[알고리즘] 소수 알고리즘

소수를 구하는 알고리즘을 알아보자. 소수의 정의를 이용한 방법 N이 소수이면 2 ~ (N-1)로 나누어 떨어지지 않는다. 이 경우 2부터 N-1까지 연산이 필요하기 때문에 O(N)의 시간복잡도가 걸린다. 약수의 특징을 이용한 방법 N이 소수가 되려면, 2이상이고, N/2 이하의 자연수로 나누어 떨어지면 안된다. (N의 약수 중에서 가장 큰 것은 N/2보다 작거나 같다) 여전히 O(N)의 시간 복잡도를 갖는다. 약수의 특징을 이용한 방법2 모든 수의 약수는 루트 N을 기준으로 대칭을 이룬다. 루트 N의 값 왼쪽에 있는 값을 기준으로 값 들을 조합해 대칭 오른쪽에 있는 수의 값을 구할 수 있다. O(루트 N)의 시간 복잡도를 가진다. 컴퓨터에서 실수는 근사값을 나타내기 때문에, 루트 N과 같은 경우는 다음 ..

[알고리즘] 소수 알고리즘(에스토스테네스 체)

에스토스테네스 체 -> 소수를 구할 때 사용하는 가장 최적화된 알고리즘이다. 알고리즘 설명 1 ) 먼저 일차원 배열을 하나 만든다. 2 ) Ch[i] == 0이면 ch[i] = 1로 바꾸고 ch[i]의 배수도 모두 1로 바꾼다. Ex ) i = 2일 때, ch[2] == 0이다. 따라서 값을 1로 바꾸고 2의 배수인 4,6,8,10,12,14도 1로 바꾼다. i = 3일 때, ch[3] == 0이다. 따라서 값을 1로 바꾸고 3의 배수인 6,9,12도 값을 1로 바꾼다. i = 4일 때, ch[4] == 1이다. 즉 소수가 아니다. 따라서 그냥 넘어간다. 구현 코드 구현은 다음과 같다.(자바) int cnt=0; int[] ch = new int[n+1]; for(int i=2; i