오래간만에 자습차 Dev-C를 이용해 소수를 세는 C++ 프로그램을 짜 보았습니다.

소수를 가르는 원리는 독일 동화 ‘수학 귀신’에서 소개한 소거법을 떠올렸습니다. 그러나 실제로는 방향을 바꿔서 짰습니다. 1은 소수가 아니니까 먼저 쳐내고, 그 다음 가장 작은 자연수부터 1과 자기 자신 사이의 수로 나머지 없이 나뉘는지를 알아보는 식이죠. 1 초과로 자기 자신 미만으로 나누어 떨어뜨릴 수 있는 수가 나오는 순간 그 수는 소수에서 뺍니다.

수학 귀신에서 쓴 방법은, 1 다음 가장 작은 자연수를 기준수로 놓은 뒤, 오름차순으로 나누어 떨어지는지 아닌지를 판별해 가는 방식입니다. 이 또한 for문의 조합으로 코딩이 가능할 것입니다.

소수 판별기 이외에 어떤 규칙을 가진 수를 뽑는 프로그램이나, 좌표를 가진 수를 가려내는 프로그램에도 도전해 보고 싶네요.

#include<iostream>
#include<cstdlib>
#include<cmath>
using namespace std;

int main()
{
cout << "<The prime number collector>" << endl;
cout << "Input the natural number to which you want to count the prime number from 1." << endl;
int N; //소수를 세고 싶은 수 범위 
cin >> N;
while(N<2){
	cout << "Please input the natural number again." << endl;
	cout << "You must write it bigger than 1." << endl;
	cin >> N; 
} //2보다 작은 정수를 넣었을 때 출력하는 경고문 
	int array[N][2]; //2차원 배열. 첫 행은 1부터 시작하는 자연수, 다음 행은 그 자연수가 소수인지 아닌지 구별하기 위한 번호표 
	for(int i=0; i<N; i++)
	{
		for(int j=0; j&lt;2; j++)
		{
		if(j==0){
			array[i][j]=i+1; //자연수 모음 
		}
		else{
			array[i][j]=1; //소수 및 소수가 아닌 자연수의 구별 번호표. 소수는 1, 소수가 아닌 자연수는 0. 
		}	
		}	
	}
array[0][1]=0; //1은 소수가 아니므로 항상 제외시키기 위한 재정의 
for(int k=1; k<N; k++) //소수 판별기. 2부터 시작. 
{
	for(int l=0; l<k; l++) //2부터 자기 자신 직전의 자연수까지 나눴을 때 나누어 떨어지는지 파악하기. 
	{
		if(array[l][1]==1) //나누는 수가 소수인지 파악하기. 
		{
	
		if(array[k][0]%(l+1)==0) //나누어지는 수를 소수로 나눴을 때 나누어 떨어진다면? 
		{
			array[k][1]=0; //그 수는 소수가 아니므로 소수가 아니라고 정의한다. 
		}
		}
		}
	}
cout << "These are every prime numbers between 1 and " << N << "." << endl;
for(int m=0; m<N; m++) //소수 나열 출력기 
{
	if(array[m][1]==1) //그 수가 소수인 경우에만 
	{
	cout << array[m][0] << " "; //출력하고 사이를 한 칸 띄어쓰기하기. 
	}	
	}
cout << endl;
system("Pause"); //명령 프롬프트 창이 강제종료되지 않게 하기 위한 장치.	
return 0;
}