Life Engineering
[BOJ 1644] 소수의 연속합 (Java) 본문
https://www.acmicpc.net/problem/1644
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
public class Main_BOJ_1644 {
static int N;
static int[] isPrime;
static ArrayList<Integer> primes=new ArrayList<>();
static int answer=0;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
N=Integer.parseInt(br.readLine());
isPrime=new int[N+1];
for (int i = 2; i <= N; i++) {
isPrime[i]=i;
}
for (int i=2; i<=N; i++) {
if (isPrime[i]==0) continue;
for (int j=i+i; j<=N; j+=i) {
isPrime[j]=0;
}
}
for (int i = 2; i <= N; i++) {
if (isPrime[i]!=0) {
primes.add(i);
}
}
int start=0;
int end=0;
int partialSum=0;
int len=primes.size();
while (true) {
if (partialSum>=N) {
partialSum-=primes.get(start++);
}
else if (end==len) {
break;
}
else {
partialSum+=primes.get(end++);
}
if (partialSum==N) {
answer++;
}
}
System.out.println(answer);
}
}
에라토스테네스의 체 + 투 포인터 문제.
'Problem Solving' 카테고리의 다른 글
[JUNGOL 2577] 회전 초밥(고) (0) | 2022.04.05 |
---|---|
[SWEA 5656] 벽돌 깨기 (Java) (0) | 2022.04.05 |
[SWEA 1767] 프로세서 연결하기 (Java) (0) | 2022.04.04 |
[BOJ 1175] 배달 (Java) (0) | 2022.04.04 |
[BOJ 14442] 벽 부수고 이동하기 2 (Java) (0) | 2022.04.03 |