알고리즘/C++
소수인지 판단하는 법 c++ 코드
고수트
2018. 11. 25. 13:15
반응형
소수란?
소수는 1이 아닌 자연수 중에서 1과 자기 자신 이외의 약수를 갖지 않는 수를 뜻한다.
문제 예시
31이 소수인지를 구하시오
팁
루트를 이용하여 시간을 반으로 줄인다.
소수가 아닌 수는 곱셈으로 표시되는 숫자이며 어차피 반대편수의 반복이기 때문이다.
예를 들면
12의 경우
2 6 / 3 4 / 4 3 / 6 2
와 같은 식의 약수의 곱이 안오는데 3 4 이후로는 앞에 나온 숫자를 자리만 바꾸어 반복하는 것이기 때문이다.
풀이
C++ 소스 코드
#include <iostream>
#include <math.h>
// 소수인지 판단
bool primeNumber(int n){
if(n<2){
return false;
}
int num = sqrt(n);
for (int i = 2; i<= num; i++){
if (n % i ==0){
return false;
}
}
return true;
}
int main() {
int N = 31;
bool result = primeNumber(N);
if(result){
std::cout << "소수\n";
} else {
std::cout << "소수 아님\n";
}
return 0;
}
반응형