강의로 돌아가기
김효재

호율성 테스트를 통과하지 못하네요..

2는 소수이니까 카운트를 1로 시작해서 2의 배수인 짝수번째는 -1을 만들어주고
3부터 홀수행은 소수인지 판단한 다음에 소수이면 카운트하고 배수들은 -1을 만들어줬는데
효율성을 통과를 못합니다 ㅠ

작성중인 코드―solution.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <string>
#include <vector>
#include <cmath>

using namespace std;

int solution(int n) {
    int answer = 1;
    vector<int> v(n+1, 1);
    for(int i=0; i<n+1; i+=2) v[i] = -1;
    for(int i=3; i<n+1; i+=2){
        if(v[i] != -1){
            bool result= true;
            for(int j=2; j<=sqrt(i); j++){
                if(i%j == 0){
                    result = false;
                    break;
                }
            }
            v[i] = -1;
            if(result == true){
                for(int j=i+i; j<n+1; j+=i){
                    if(v[i] != -1) v[i] = -1;
                }
                answer++;
            }
        }
    }
    return answer;
}
0 개의 답변
답변 쓰기
이 입력폼은 마크다운 문법을 지원합니다. 마크다운 가이드 를 참고하세요.