[프로그래머스] 소수 찾기

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12921

프로그래머스

풀이와 코드

사실 이 문제는 내가 혼자 풀면 시간이 꽤 걸릴거 같아서 chatGPT의 도움을 받았다.

처음으로 작성한 코드를 보여주니 바로 효율성을 말하면서 새로운 코드를 보여줬다 ㅋㅋ

'에라토스테네스의 체' 알고리즘을 사용해야한다고 친절한 설명까지... 역시 최고의 선생님!

개념은 이해가 되는데 내가 혼자 효율적인 코드를 짤 수 있을지 미지수다...

다음에 잊혀질거 같을 때 다시 혼자 코드 짜봐야겠다!

// chat GPT 코드
#include <string>
#include <vector>
#include <iostream>

using namespace std;

int solution(int n) {
    vector<bool> isPrime(n + 1, true);  // 초기에 모든 숫자를 소수로 가정
    isPrime[0] = isPrime[1] = false;  // 0과 1은 소수가 아님
    
    for (int i = 2; i * i <= n; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;  // i의 배수는 소수가 아님
            }
        }
    }

    int count = 0;
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            count++;
        }
    }
    
    return count;
}

// 내가 작성한 초안 코드
#include <string>
#include <vector>
#include <iostream>

using namespace std;

int solution(int n) {
    int answer = 0;
    bool isPrimeNumber;
    
    for(int i=2; i<=n; i++){
        for(int j=2; j<i; j++){
            if (i%j==0){
                isPrimeNumber = false;
                break;
            }
            
            isPrimeNumber = true;
        }
        
        if(isPrimeNumber){
            answer++;
        }
    }
    
    return answer + 1;
}