[알고리즘/백준] 소수 판별

소수는 1을 제외하고 나눴을 때 0이 되는 수가 자신밖에 없는 수를 말한다.

예를 들어서, 2는 2로 나누는 것을 제외했을 때 0이 되는 수가 없어서 소수가 된다.

이를 기본적인 코드로 구현했을 때 다음과 같다.

void find(int num){
	int count=0;
	
    //1은 제외
    if(num==1){
    	cout<<"소수가 아님";
    }
    
    //나머지 수 계산
    for(int i=2; i<=100; i++){
    	if(num%i==0)
        	count+=1;
   }
   
   //출력
   if(count==1){
   		cout<<"소수입니다!";
   }
   else{
   		cout<<"소수가 아님";
   }
}

희망하는 범위의 수까지 for반복문을 통해, 자신과 범위의 수 전체를 비교한다.

임의의 변수를 두어 자신과 특정 수를 나눌 때 나머지가 0인 경우가 존재하면 1을 더하도록 하였다.

for문을 모두 반복한 후, 임의의 변수가 1이란 것은 자기 자신을 나누는 수가 자신밖에 없다는 말이기에 소수임을 뜻한다고 해석할 수 있다.

 

for문을 반복할 때, 반드시 자신에 해당하는 수도 나누게 되며 이때 나머지는 항상 0이기에 임의의 변수는 1부터 시작하게 된다. 나누었을 때 0이 되는 수가 더 존재한다면 임의의 변수는 1을 초과한다.

---

기능적인 구현의 형태는 다음과 같다.

백준 '1978번 소수찾기'에서 구현을 했다.

#include<iostream>
using namespace std;

int find(int num) {
	int dec = 0;
  
  //1 제외
	if (num == 1) {
		return 0;
	}
  //나머지 수 계산
	for (int i = 2; i <= 1000; i++) {
		if (num % i == 0)
			dec += 1;
	}
  
  //출력
	if (dec == 1) {
		return 1;
	}
	else {
		return 0;
	}
}

int main() {
	int num;
	int arr[1000];
	int dec = 0;
	cin >> num;
	for (int i = 0; i < num; i++) {
		cin >> arr[i];
		dec+=find(arr[i]);
	}
	cout << dec;
}

 

⛏️ 깃헙 해당 코드 주소

GitHub - minjeongss/Algorithm: 알고리즘 문제 풀이 Repository 🚀

: 코드 전체를 가독성 있게 보거나, 다른 백준 문제 풀이를 참고할 수 있다.