[프로그래밍] 소수출력 알고리즘

여기서 사용한 소수출력 알고리즘은 N이 소수인지 판별하기 위해서 2부터 sqrt(N)이하의 자연수로 일일히 나누어보아서 그 중 하나라도 나누어지게 되면 소수가 아니라고 출력하고, 만약 나누어지지 않는다면 소수라고 출력하는 알고리즘이 하나 있고,

두번째 알고리즘은 N개의 소수를 출력하는데 최적화 된 코드로 N개의 배열을 정의한 다음 소수라고 판별된 것을 배열에 넣어주고, 또 소수를 판별하기 위해서는 그 배열에 있는 수로만 나누어보아서 나누어떨어지는 수가 존재하면 합성수라고 판별하고, 나누어떨어진 수가 존재하지 않으면 소수라고 판별하는 방식으로 진행하였다.

아래는 그와 관련된 소스코드이다.

printPrime()과 isPrime()이 첫 번째 알고리즘과 관련된 내용이고, getPrimeArr()와 printArr()가 두 번째 알고리즘과 관련된 내용이다.

#include <stdio.h>
#include <windows.h>

#define SIZE 10

void printPrime(int);
void getPrimeArr(int[]);
void printArr(int[], int);

int main(void){
	int i;
	LARGE_INTEGER liCounter1, liCounter2, liFrequency;
	QueryPerformanceFrequency(&liFrequency);
	QueryPerformanceCounter(&liCounter1);
	int arr[SIZE]={};
	getPrimeArr(arr);
	//printArr(arr, sizeof(arr)/sizeof(int));
	QueryPerformanceCounter(&liCounter2);
	printf("\n");
	printf("Time: %f\n", (double)(liCounter2.QuadPart-liCounter1.QuadPart)/(double)liFrequency.QuadPart);
	printf("\n");
	QueryPerformanceFrequency(&liFrequency);
	QueryPerformanceCounter(&liCounter1);
	printPrime(SIZE);
	QueryPerformanceCounter(&liCounter2);
	printf("\n");
	printf("Time: %f\n", (double)(liCounter2.QuadPart-liCounter1.QuadPart)/(double)liFrequency.QuadPart);
	printf("\n");
}

bool isPrime(int num){
	int i=2;
	if(num<2)
		return false;
	while(i*i<=num){
		if(num%i == 0)
			return false;
		i++;
	}
	return true;
}

void printPrime(int size){
	int i=0, j=2;
	while(i<size){
		if(isPrime(j)){
		//	printf("%d; ", j);
			i++;
		}
		j++;
	}
}

void getPrimeArr(int arr[]){
	int i, j=0;
	for(i=2; j<SIZE; i++) {
		int k=0, state=0;
		if(j==0){
			arr[j++]=i;
			continue;
		}
		for(k=0; arr[k]*arr[k]<=i; k++){
			if((i%arr[k])==0){
				state = -1;
				break;
			}
		}
		if(state==0){
			arr[j++]=i;
		}
	}
}

void printArr(int arr[], int num){
	int i;
	for(i=0; i<num; i++)
		printf("%d; ", arr[i]);
}