-
소수는 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; }
⛏️ 깃헙 해당 코드 주소
: 코드 전체를 가독성 있게 보거나, 다른 백준 문제 풀이를 참고할 수 있다.
'프로그래밍 > C++' 카테고리의 다른 글
[자료구조 복습] Linked List (0) 2022.10.04 [알고리즘/백준] 아스키코드 (0) 2022.07.31 [알고리즘/백준] 재귀함수 (0) 2022.07.19 쓰레드(thread) (0) 2022.01.15 [진수 변환] 16진수/10진수/8진수 입출력 변환 (0) 2021.08.29 [프로그래머스] 더 맵게 / 힙 / C++ / 문제 풀이 🔍 (0) 2021.06.28 [C++] STL Priority Queue(우선순위 큐) 활용법 (0) 2021.06.28 [C++] STL Dequeue 활용법 (0) 2021.06.28 댓글