5-G 배열 크기 질문

안녕하세요 sol님ㅎㅎ

일단, 4000004를 해도 상관 없습니다.

#include <bits/stdc++.h>
using namespace std;  
bool che[4000004];
int n, a[4000004], p, lo, hi, ret, sum; 
 
int main(){
	scanf("%d", &n); 
    for(int i=2; i<=n; i++){
		if(che[i]) continue;
		for(int j=2*i; j<=n; j+=i){
			che[j] = 1;
		}
	}
	for(int i=2; i<=n; i++){
		if(!che[i]) a[p++] = i;
	}  
    while(1){
        if(sum >= n) sum -= a[lo++];
        else if(hi == p)break;
        else sum += a[hi++];
        if(sum == n) ret++;
    } 
    printf("%d\n", ret); 
}

이 코드를 볼까요? 4000004로 했음에도 불구하고 제출하면 맞았다고 뜰겁니다.

다만... sol님 코드를 보면 딱히 틀린 부분은 못 찾겠습니다. 여러번 봤는데도.. 솔직히 잘 모르겠네요.

제 코드와 다른 점은 max 부분 말고는 없습니다.

일단은 그냥 제 코드 좀 참고하시고 넘어가시면 될 것같습니다.

그러나 수정되어야할 코드는 있어요.

void makePrime(){
	a[0] = true;
	a[1] = true;
	for(int i = 2; i * i <= MAX; i++){
		if(a[i]) continue;
		for(int j = i * 2; j <= MAX; j += i){
			cout << j << "\n";
			a[j] = true;
		}
	}

이부분이요. 이렇게 되면 MAX가 참조되게 됩니다. 예를 들어 40을 넣었을 때 저 j에는 40이 찍히게 되죠. 즉 배열을 40까지 만들어 놓고 40 인덱스를 참조하게 되는 것입니다.

다만, 이부분은 제 잘못이 큽니다. 제 에라토스테네스 채를 보면 해당 부분이 헷갈리게 되어있는 거 같아요.

해당부분은 다음과 같이 수정되었습니다. (오늘 업데이트될 예정입니다 - 교안)

앞으로는 이코드를 기반으로 에라를 작성해주시면 됩니다.

다음 코드는 max_n까지의 소수를 만들어서 출력하는 코드입니다.
#include<bits/stdc++.h>
using namespace std; 

const int max_n = 40;
bool che[max_n + 1];
// 예를 들어 40을 넣었을 때 che[40]이 참조가 되므로 max_n + 1을 넣어야 함. 
// max_n까지의 소수를 만드는 함수. 
vector<int> era(int mx_n){ 
    vector<int> v; 
    for(int i = 2; i <= mx_n; i++){
        if(che[i]) continue;
        for(int j = 2*i; j <= mx_n; j += i){ 
            che[j] = 1;
        }
    }
    for(int i = 2; i <= mx_n; i++) if(che[i] == 0)v.push_back(i); 
    return v; 
}
int main(){ 
	vector<int> a = era(max_n);
	for(int i : a) cout << i << " ";
}

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제가 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

인프런 커뮤니티 질문&답변