강의로 돌아가기
김영상

수행시간 초과

정확도 테스트에서는 다 통과 됬는데 마지막 효율성 테스트 4개에서 계속걸리네요.
몇개 만들어봣는데 다 효율성테스트에서 걸리는데 어떡하죠.

----------------------------------------- < 1 > -----------------------------------------
int solution1(int n) {

unsigned int i=2,j,pnum = 1;
while (i <= n) {
    pnum++;
    j = 2;
    while (j*j <= i) {
        if (i%j == 0) { pnum--; break; }
        j++;
    }
    i++;
}
return pnum;

}

----------------------------------------- < 2 > -----------------------------------------
int solution2(int num) {
int pnum = 0,snum=sqrt(num);
int *arr;
arr = new int[num];
for (int i = 0; i < num; i++)
arr[i] = 1;

for (int i = 2; i <= snum; i++) { 
    if (arr[i-1] != 0) {
        for (int j = i; j <= num; j++) {
            if (j != i && j % i == 0) { 
                arr[j-1] = 0;
            }
        }
    }
}
for (int i = 1; i < num; i++)
    if (arr[i] != 0)
        pnum++;
return pnum;

}

----------------------------------------- < 3 > -----------------------------------------
int solution3(int n) {

unsigned int pnum = 3;      // 2, 3

if (n <= 2) return 1;
else if (n <= 3) return 2;
else if (n <= 5) return 3;
else {
    for (int i = 7; i <= n; i += 6) {
        if ((i % 10) % 2 == 1 && (i % 10) != 5) {
            pnum++;
            for (int j = 2; j*j <= i; j++) {
                if (i%j == 0) { pnum--; break; }
            }
        }
    }
    for (int i = 11; i <= n; i += 6) {
        if ((i % 10) % 2 == 1 && (i % 10) != 5) {
            pnum++;
            for (int j = 2; j*j <= i; j++) {
                if (i%j == 0) { pnum--; break; }
            }
        }
    }
}
return pnum;

}

----------------------------------------- < 4 > -----------------------------------------
int solution4(int n) {
int mod;
vector v={2};
v.reserve(n);
if (n == 2) return 1;

for (int i = 3; i <= n; i++) {
    mod = 0;
    v.push_back(i);
    for (int j = 0; j < v.size()-1; j++) {
        if (i%v[j] == 0) { v.pop_back(); break; }
    }
}
return v.size();

}

1 개의 답변
Demi

안녕하세요. 다른 분들의 팁 을 참고해보시는게 어떨까요?

답변 쓰기
이 입력폼은 마크다운 문법을 지원합니다. 마크다운 가이드 를 참고하세요.