[알고리즘] 소수판별
💡 소수 Prime Number
1보다 큰 정수 p의 양의 약수가 1과 p뿐일 때 p를 소수라고 하며 1보다 큰 정수 n이 소수가 아닐 때 n을 합성수(Composite number)라고 한다.
💡 관련문제: 프로그래머스 Level 1 소수 찾기
1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)
첫번째 시도
#include <string>
#include <vector>
#include <cmath>
using namespace std;
int solution(int n) {
int answer = 1;
int sq;
int div;
sq = ceil(sqrt(n));
for(int i=3;i<=n;i++) {
div = (i>=sq) ? sq : i;
for(int j=2;j<div;j++) {
if(i%j==0) {
break;
} else if(j==div-1) {
answer++;
}
}
}
return answer;
}
=> 시간 초과
두 번째 시도
#include <string>
#include <vector>
#include <cmath>
using namespace std;
int solution(int n) {
int answer = 1;
int div;
vector<int> v;
v.push_back(2);
for(int i=3;i<=n;i++) {
if(i%2!=0) {
v.push_back(i);
}
}
div = ceil(sqrt(n));
for(int i=2;i<=div;i++) {
for(int j=2;j<v.size();j++) {
if(v.at(j)%i==0 && v.at(j)/i!=1) {
v.erase(v.begin()+j);
}
}
}
answer = v.size();
return answer;
}
=> 시간 초과
세 번째 시도
#include <string>
#include <vector>
#include <cmath>
using namespace std;
int solution(int n) {
int answer = 0;
int div = ceil(sqrt(n));
vector <int> arr;
for(int i=1;i<=n;i++) {
arr.push_back(i);
}
arr[0] = 0;
for(int i=2; i<=div; i++){
if(arr[i-1]){
for(int j = i * i; j <= n; j += i)
arr[j-1] = 0;
}
}
for(int i = 0; i < n; i++){
if(arr[i]!=0) {
answer++;
}
}
return answer;
}
=> 에라토스테네스의 체
💡 하나씩 나눠보기
단일 숫자의 소수 여부 판별 시 유용
- 2를 제외한 짝수는 제외
- √n까지 나눠보기
=>O(√n)
💡 에라토스테네스의 체
대량의 소수를 한 번에 판별할 때 유용
- 배열을 생성하여 초기화한다.
- 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다.(지울 때 자기자신은 지우지 않고, 이미 지워진 수는 건너뛴다.)
- 2부터 시작하여 남아있는 수를 모두 출력한다.
Author And Source
이 문제에 관하여([알고리즘] 소수판별), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kji990607/소수-찾기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)