[알고리즘] 소수판별, 투포인터, 구간합

소수 판별 알고리즘

• 소수
  1보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어 떨어지지 않는 자연수
• 약수의 성질
  모든 약수가 가운데 약수를 기준으로 곱셈 연산에 대해 대칭을 이룸
  따라서 소수를 판별할 때, 가운데 약수까지만 확인하면 됨(Math.sqrt(x)

에라토스테네스의 체 알고리즘

• 다수의 자연수에 대하여 소수 여부를 판별할 때 사용
• N보다 작거나 같은 모든 소스를 찾을 때 사용
• 동작과정
  1. 2부터 N까지의 모든 자연수를 나열
  2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾음
  3. 남은 수 중에서 i의배수를 모두 제거(i는 제거하지 않음)
  4. 더 이상 반복할 수 없을 때까지 2번과 3번의 과정 반복
• 성능 분석
  - 시간 복잡도 O(NloglogN)
  - 다수의 소수를 찾아야하는 문제에서 효과적
• 각 자연수에 대한 소수 여부를 저장 - 메모리 많이 필요

boolean[] arr = new boolean[max + 1];
Arrays.fill(arr, true);

// 소수 구하기 - 에라토스테네스의 체
for (int i = 2; i <= Math.sqrt(max); i++) {
	if (arr[i]) {
		int j = 2;
		while (i * j <= max) {
			arr[i * j] = false;
			j++;
		}
	}
}

투 포인터

• 리스트에서 순차적으로 접근해야 할 때 두개의 점의 위치를 기록하면서 처리
• 리스트에 담긴 데이터에 순차적으로 접근할 때 시작점과 끝점 2개의 점으로 접근할 데이터의 범위를 표시할 수 있음
• 특정한 합을 가지는 부분 연속 수열 찾기

구간합

• 구간합 문제
  연속적으로 나열된 N개의 수가 있을 때 특정 구간의 모든 수를 합한 값을 계산
• 접두사 합 : 배열의 맨 앞부터 특정 위치까지의 합을 미리 구해 놓은 것

int start = 0;
int end = 0;
int sum = 0;
    
//가능할때까지 end값 증가
for(int start = 0; start < n; start++){
	while(sum < m && end < n){
    		sum += arr[end];
        	end++;
        }
	if (sum == m)
		count++;
        sum -= arr[start]
}