C언어 1부터 100까지의 소수 탐색기의 구현 (with source)

읽어주셔서 감사합니다.

지난 블로그의 글을 응용해서 제목과 같이 1 ~ 100까지의 소수를 탐색하는 프로그램을 만들어 보겠습니다.

(참고로 이 블로그는 최대한 이해가 쉽도록 쓰는 글입니다. 고로 프로그램의 성능은 떨어집니다. 고성능의 소수 탐색기가 필요한 분들은 아래의 제 signature블로그 글을 참고해주세요)

https://kms-program.tistory.com/12

KMS04 : C++ 소수탐색 프로그램 Ver3 (source)

---

코드

오늘은 변 내용이 없고, 사실성 이전에 만든 소수판독 함수의 응용 버전이며, 주석을 꽤나 자세하게 적어놓았기에 별다른 설명을 적지 않겠습니다.

소수 판독 함수 포스팅

 

소스가 필요하신 분들은 Ctrl + C Ctrl + V로 퍼가시면 됩니다

#include <stdio.h>
#define _CRT_SECURE_NO_WARNINGS

//n이 소수인지 아닌지를 판변해, 소수면 1, 아니면 0을 반환
int isPrime(int n) {
	int div;
	for (div = 2; div < n; div++) {
		if ((n % div) == 0) { //만약 n이 div로 나누어진다면
			return 0; //n은 소수가 아님
		}
	}
	return 1;
}

int main(void) {
	int num;
	for (num = 2; num <= 100; num++) { //2 ~ 100까지의 모든 정수 num에 대해
		if (isPrime(num) == 1) { //num이 소수라면
			printf("%d \n", num); //num을 출력
		}
	}
	return 0;
}

 

+ 추가적으로 간단하게 만들어본 가독성이 어느정도 존재하면서 효율적인 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>

#define FIN	100

using namespace std;

vector<int> V(0);

int F(int S, int N) {
	static int C = 0;

	if (S >= 0) { 
		C = S; 
		return 1;
	}

	if (C) {
		N += 2;
		C = 0;
	}
	else {
		N += 4;
		C = 1;
	}
	return N;
}

int I(int N) {
	int D, i = 0;
	for (D = V.at(i++); D <= (int)floor(sqrt((double)N)); D = V.at(i++)) {
		if (!(N % D)) { return 0; }
	}
	return 1;
}

inline void R(int N) {
	printf("%d \n", N);
	V.push_back(N);
}

int main(void) {
	int N;
	R(2);
	R(3);
	
	F(1, 0);
	for (N = 5; N <= FIN; N = F(-1, N)) {
		if (I(N)) {
			R(N);
		}
	}
	return 0;
}

---

사용방법

입력 : 없음

출력 : 1 ~ 100까지의 모든 소수 출력

종료 : 출력후 종료

---

실행화면

감사합니다