[프로그래머스/Lv.0] 합성수 찾기

1. Input

1) 자연수 n

 

2. Output

1) n 이하의 합성수의 개수

 

3. Constraint

1) 1 <= n <= 100

 

4. Example

Input: n=10 -> Output: 5

설명: 10 이하의 합성수는 10, 9, 8, 6, 4의 5개

 

5. Code

1) 첫 코드(2022/10/26)

int answer = 0;
for(int i=n ; i>=1 ; i--){
    int count = 0;
    for(int j=1 ; j<=i ; j++){
        if(i%j==0)
            count++;
        if(count>=3){
            answer++;
            break;
        }
    }
}
return answer;

2) 4 이상의 짝수는 모두 합성수임을 이용한 수정 버전(2022/10/26)

int answer = 0;
for(int i=1 ; i<=n ; i++){
    if(i%2==0 && i>=4){
        answer++;
        continue;
    }
    int count = 0;
    for(int j=1 ; j<=i ; j++){
        if(i%j==0)
            count++;
        if(count>=3){
            answer++;
            break;
        }
    }
}
return answer;

  - 1번보다 조금 더 빨라짐