[DS] 소수 찾기

# 소수 판별

- 소수: 1과 자신 이외의 수로는 나누어지지 않는 수

 

[코드]

int prime(int n) {
	if (n < 2) return 0; // n이 2보다 작으면 1이므로 소수가 아님
	for (int i = 2; i < n; i++) { // 2부터 n-1까지의 수를 탐색 
		if (n % i == 0) return 0; // i로 나누어서 1이 되는 경우가 있다면 소수 X
	}
	return 1;
}

* n이 2인 경우에는 i<n 조건문이 거짓이 되므로 나누는 과정 없이 즉시 for문을 탈출함

 

[실행결과]

- main 함수에서 prime(3)을 실행한 후 참이면 아래와 같이 출력되도록 코드를 작성

 

 

 

# 소수 찾기

예제) 1000보다 작은 소수 찾는 프로그램

 

[코드]

#include<stdio.h>

void prime_number(int num);

int main() {
	int maxnum = 1000;
	prime_number(maxnum);
}

void prime_number(int num) {
	int prime, i, j;
	for (i = 2; i <= num; i++) {
		prime = 1;
		for (j = 2; j < i; j++) { // 2에서 i-1 사이의 수
			if (i%j == 0) { // j로 나누었을 때 나머지가 0이면
				prime = 0; // 소수가 아님
				break;
			}
		}
		if (prime) printf("%3d ", i); // prime=1을 유지한 채로 for문을 탈출했다면 그 수를 출력
	}
}

 

[실행결과]