강의로 돌아가기
김영상

수행시간 초과

정확도 테스트에서는 다 통과 됬는데 마지막 효율성 테스트 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

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

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