c언어 1644번 소수의 연속합 (백준)

#include <stdio.h>

char a[4000001] = {1, 1,}; //소수이면 0, 아니면 1
long long int sosu[300000] = {}; //소수들의 누적합을 넣는 배열

int main(void) {
	int n, cnt = 1;
	scanf("%d", &n);
	
	for(long long int i=2; i<=n; i++) { //에라토스테네스 체
		while(a[i]) i++; //소수가 아닐경우 다음 걸로
		sosu[cnt] += sosu[cnt-1]+i; //소수의 누적합
		cnt++; 
		for(long long int k = i*i; k<=n; k+=i) { //소수 구하기 (중요한 것은 int의 범위를 넘어가니 i도 long long int로)
			a[k] = 1;
		}
	}
	
	
	int ans = 0;
	int left = 0, right = 0;
	while(left <= right) { //두 포인터와 누적합을 이용한다. 만약 왼쪽 포인터가 오른쪽을 추월하면 반복문을 종료한다.
		int tmp = sosu[right]-sosu[left];
		if(tmp > n) left++; //부분합이 크면 왼쪽을
		else if(tmp < n) { //부분합이 작으면 오른쪽을
			if(right == cnt) break; //오른쪽 포인터가 더이상 이동 할 곳이 없으면
			right++;
		}
		else { //일치한다면 왼쪽을 (실제로는 오른쪽 왼쪽 둘다 올려도 상관은 없다)
			ans++; //일치할 경우
			left++;
            if(right == cnt) break; //오른쪽 포인터가 더이상 이동 할 곳이 없으면
		}
	}
	
	printf("%d", ans);
	
}

 

 

풀이 : 에라토스테네스 체, 누적합과 두 포인터

 

1. 소수인지아닌지를 저장할 배열과, 소수들을 누적할 배열을 준비합니다.

2. 에라토스테네스의 체를 이용하여, 소수들을 구하고, 소수들을 구할 때마다 누적합을 구합니다.

3. 두 포인터를 이용하여, 누적합의 범위를 조절해서 n과 같으면 ans을 증가시키며 (왼쪽 포인터도 증가)

n보다 작으면 오른쪽 포인터를

n보다 크면 왼쪽 포인터를 증가시키며

왼쪽 포인터가 오른쪽 포인터를 추월하거나, 오른쪽 포인터가 더이상 갈 곳이 없다면 반복문을 종료한다.

4. 연속된 소수로 n을 만들 수 있는 개수인 ans을 출력한다.

 

추가

속도를 최대한 빠르게 하기위해선, continue 같이 시간을 많이 잡아먹는 것은 사용해선 안됩니다. (물론 쓰지 말란 말은 아니며, 사실 전 왕초보여서 현장에서는 어떻게 쓰이는지도 모릅니다)

 

또한 if문도 많이 사용되면 속도가 느려지므로, 특정 부분에서만 if문이 작동되도록 하는 것이 좋다 (물론 코드는 길어진다)

 

while(a[i]) i++; 이부분을

if(a[i]) continue; 이렇게 하면 너무 느려져서 통과가 안된다.

 

https://www.acmicpc.net/problem/1644

1644번: 소수의 연속합