[27주차_목요일] 소수의 연속합

[baexxbin]

• 사이트: 백준(BOJ)
• 문제: 소수의 연속합
• 번호: 1644

### 🤔 시간복잡도 고려사항



### 💡 풀이 아이디어

[KodaHye]

🤔 시간복잡도 고려사항

• $1 \leq N \leq 4,000,000$
• 1부터 N까지 수 중에서 소수를 구해야 되는데, 반복문을 통해서 소수판별을 한다면 시간 초과가 발생함 ($N \times N$)
• 에라토스테네스를 통해 1부터 N까지의 소수 구하기: $N log(logN)$

💡 풀이 아이디어

에라토스테네스의 체를 통해 N까지 숫자에서 소수를 판별하고, 투 포인터를 통해 연속합이 N이 되는 경우의 수 구하기

변수	설명
boolean[] isNotPrime	isNotPrime[i]가 true이면 소수가 아님, false이면 소수

• boolean[] isNotPrime(int N): 에라토스테네스의 체를 이용해서 N까지 수들을 소수 판별하기

  • boolean[] isNotPrime: i가 소수인지 아닌지 저장

  boolean[] isNotPrime = new boolean[n + 1];
  
  isNotPrime[0] = true;
  isNotPrime[1] = true;
  
  for(int i = 2; i <= Math.sqrt(isNotPrime.length); i++) {
  	if(isNotPrime[i]) continue;
  	
  	for(int j = i * i; j < isNotPrime.length; j += i) {
  		isNotPrime[j] = true;
  	}
  }
  
  return isNotPrime;

• int getCount(boolean[] isNotPrime, int N): 소수의 누적합을 통해 N을 몇 개 만들 수 있는지 확인

  • 투포인터를 이용해서 연속된 누적합(sum)을 구함
  • s와 e의 초기값을 2로 설정 (제일 작은 소수, 근데 0으로 설정해도 됨)
  • 누적합 < n일 경우
    • 소수가 나올 때 까지 e값 늘려주기
    • 소수가 나왔다면, sum에 더해주고, 반복문에서 빠져나오기
  • 누적합 >= n일 경우
    • 누적합 == n일 때, count 값 증가시키기
    • sum에서 s 빼주기
    • 소수가 나왔다면 반복문에서 빠져나오기

[jmxx219]

🤔 시간복잡도 고려사항

• 1 ≤ N ≤ 4,000,000
• 소수 리스트를 구해야하는데, 숫자마다 소수를 판별하면 시간 초과 발생 -> 에라토스테네스의 체 이용
• 연속된 소수의 합 -> 투 포인터 이용

💡 풀이 아이디어

1. 에라토스테네스의 체 이용해서 소수 리스트 구하기

private static void findPrimeNumber() {
	boolean[] isPrime = new boolean[N + 1];
	Arrays.fill(isPrime, true);

	for (int i = 2; i <= Math.sqrt(N); i++) {
		if(!isPrime[i]) continue;
		for(int j = i * i; j <= N; j += i) {
			isPrime[j] = false;
		}
	}

	for (int i = 2; i <= N; i++) {
		if(isPrime[i]) primeNumbers.add(i);
	}
}

2. 투 포인터로 연속된 소수의 합 구하기

int count = 0;
int lo = 0, hi = 0;
int sum = 0;
while (true) {
	if(sum < N) {
		if(hi == primeNumbers.size()) break;
		sum += primeNumbers.get(hi++);
	}
	else {
		sum -= primeNumbers.get(lo++);
	}

	if(sum == N) count++;
}

[yeongleej]

🤔 시간복잡도 고려사항

• N <= 4,000,000

=> O(N) or O(NlogN)으로 생각

💡 풀이 아이디어

1. 에라토스테네스의 체로 소수 N까지의 소수 구하기
2. 투포인터를 활용해서 합이 N인 경우의 수 구하기

        for(int i = 2; i <= Math.sqrt(N); i++){ 
            if(isPrime[i]){ 
                //  i의 배수 제거
                for(int j = i*i; j<= N; j += i){
                    isPrime[j] = false;
                }
            }
        }

• s: 합의 시작점, e: 끝점 => N보다 작으면 e증가, N보다 커지면 s증가

	while(s <= e) {
		if(total == N) {
			cnt++;
			total -= pList.get(s);
			s++;
		}
		else if(total > N) {
			total -= pList.get(s);
			s++;
		}
		else {
			e++;
			if(e >= pList.size()) break;
			total += pList.get(e);
		}
	}

[baexxbin]

🤔 시간복잡도 고려사항

• N <= 4,000,000
• O(NlogN) 이내

💡 풀이 아이디어

• 소수 리스트 구하기 → 에라토스테네스의 체

private static void getPrimeLst() {
        boolean[] isPrime = new boolean[N + 1];
        Arrays.fill(isPrime, true);

        isPrime[0] = isPrime[1] = false;
        for (int i = 2; i <= Math.sqrt(N); i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= N; j += i) {
                    isPrime[j] = false;
                }
            }
        }

        for (int i = 2; i <= N; i++) {
            if (isPrime[i]) primes.add(i);
        }
    }

• 소수 리스트로 만들 수 있는 N의 경우 구하기 → 투포인터 이용

int s = 0, e = 0;
        int cnt = 0;
        int sum = 0;

        while (true) {
            if (sum==N) cnt++;
            if (sum < N) {
                if (e == primes.size()) break;
                sum += primes.get(e++);
            }
            else{
                sum -= primes.get(s++);
            }
        }

        System.out.println(cnt);

[jewan100]

🤔 시간복잡도 고려사항

• 1 ≤ N ≤ 4,000,000 → $10^6$이므로 O(N logN)이하로

💡 풀이 아이디어

• 소수를 판별하기 위해서 에라토스테네스의 체를 이용

  isPrime[0] = isPrime[1] = true;
  ArrayList<Integer> prime = new ArrayList<>();
  for (int i = 2; i < n + 1; i++) {
      if (isPrime[i])
          continue;
      prime.add(i);
      for (int j = i * 2; j < n + 1; j += i)
          isPrime[j] = true;
  }

• 연속된 소수의 합을 이용해야 하기 때문에 포인터를 이용해서 구현

  int l = 0, r = 0, sum = 0;
  while (r < prime.size()) {
      sum += prime.get(r);
      while (sum > n && l <= r)
          sum -= prime.get(l++);
      if (sum == n)
          cnt++;
      r++;
  }