문제 설명
1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)
코드 풀이
이 문제는 다른 문제들과 다르게 시간복잡도에 주의해야했다.
처음에 이중 for문을 쓰면서 이거 안될거 같다 했는데 혹시나가 역시나
소수를 찾는 알고리즘은 꽤 많이 알려져 있고 인터넷검색에도 있기에 어렵진 않았다.
내가 참고한 사이트는 아래이다.
[알고리즘] 소수(Prime Number) 구하기 - 에라토스테네스의 체 (Java) (tistory.com)
[알고리즘] 소수(Prime Number) 구하기 - 에라토스테네스의 체 (Java)
소수 소수(prime number)는 정수론의 가장 중요한 연구 대상 중 하나로, 양의 약수가(1보다 큰 자연수) 1과 자기 자신만을 약수로 가지는 수를 의미한다. 소수의 반대말로, 세 개 이상의 양의 약수를
loosie.tistory.com
내가 이해한대로 간단하게 작성 해보고자 한다.
소수 정의는 넘어가고 코드 설명만 할 것이다.
bool isPrime(int n){
for(int i = 2; i*i<=n; i++){
if(n % i == 0){
return false;
}
}
return true;
}
이것이 내가 사용한 식이다.
가장 단순한 식은 분명
bool isPrime(int n){
for(int i = 2; i<=n; i++){
if(n % i == 0){
return false;
}
}
return true;
}
이것일 것이다. 위의 코드와의 차이첨은 i를 제곱했느냐 아니냐의 차이
이 차이 덕분에 N인 복잡도가 N½로 줄어 들게 된다.
백문이 불여일견 몇가지를 예시로 들어 해보겠다.
ex) n = 5일 경우
i = 2 : 2*2<= 5가 참이므로 실행
5는 2로 나뉘지 않으므로 다음 수로
i = 3 : 3*3 <= 5가 거짓이므로 for문을 끝내게 되고
참을 리턴하게 된다.
ex) n = 15일 경우
i = 2 : 2*2 <= 15가 참이므로 실행
15는 2로 나뉘지 않으므로 다음수로
i = 3 : 3*3 <= 15가 참이므로 실행
15는 3으로 나뉘므로 for문을 끝내고 거짓을 리턴하게된다.
ex) n = 7일 경우
i = 2 : 2*2 <= 7이 참이므로 실행
7은 2로 나뉘지 않으므로 다음수로
i = 3 : 3*3 <= 7 이 거짓이므로 for문을 끝내게 되고
참을 리턴하게 된다
위의 예시들을 보면 i가 num만큼 반복하지 않았음에도 값을 반환한다는 걸 알 수 있다.
자세한 원리는 위에 참고한 링크를 보길 바란다.(어렵..)
암튼 위를 알고 코드를 짜보자
먼저 보기 편하게 사용자 함수로 소수 판단문을 작성하였다.
bool isPrime(int n){
for(int i = 2; i*i<=n; i++){
if(n % i == 0){
return false;
}
}
return true;
}
2에서부터 n까지 실행하는 for문을 작성하고 isPrime에 i값을 전달하면 각 수에대해 판단하게 된다.
맞다면 true를 반환하기에 answer값이 증가한다.
int solution(int n) {
int answer = 0;
for(int i = 2; i <= n; i++){
if(isPrime(i)){
answer++;
}
}
return answer;
}
전체코드
#include <string>
#include <vector>
using namespace std;
bool isPrime(int n){
for(int i = 2; i*i<=n; i++){
if(n % i == 0){
return false;
}
}
return true;
}
int solution(int n) {
int answer = 0;
for(int i = 2; i <= n; i++){
if(isPrime(i)){
answer++;
}
}
return answer;
}
'코딩테스트 > 프로그래머스' 카테고리의 다른 글
프로그래머스 [PCCE 기출문제] 9번 지폐접기 (4) | 2024.09.13 |
---|---|
프로그래머스 LV1 C++ 문자열 내 p와 y의 개수 풀이 (0) | 2024.04.16 |
프로그래머스 LV1 C++ 문자열 내마음대로 정렬하기 풀이 (0) | 2024.04.16 |
프로그래머스 LV1 C++ 두 정수 사이의 합 풀이 (0) | 2024.04.16 |
프로그래머스 C++ LV1 나누어 떨어지는 숫자 배열 풀이 (0) | 2024.04.05 |