[C] 소수 구하는 프로그램

아래 코드는 1부터 10만 사이의 소수를 구한다.

​

복잡한 알고리즘도 아니고 한번 더 생각해서 식만 조금 수정했을 뿐인데 시간 차이가 이렇게 많이 난다.

​

물론 내가 작성한 코드보다 더 빠른 소수 구하는 코드가 많다.

​

내가 말하고자 하는건 내가 코딩한 소수 구하는 코드가 빠르고 좋다가 아니라

(아래 코드는 대충 막 짠 코드라 코드도 지저분하고 좋은 알고리즘에 비교하면 정말 느리다.)

​

한번만 더 생각해서 코딩하면 더 나은 코드를 작성할 수 있으니 평소에 코딩할 때 항상 어떻게 코딩해야 더 좋은 코드가 될지 생각하면서 코딩하는 습관을 가졌으면 좋겠다.

​

사용자는 0.7초는 기다리지만 14초는 기다리지 않는다.

#pragma warning(disable : 4996)

#include <stdio.h>
#include <Windows.h>
#include <time.h>
#include <math.h>

#define TEMP 100000

void first();  // 단순무식
void second(); // 모든 짝수는 소수가 될수 없으므로 홀수로 증가
void third();  // 소수는 1과 자기 자신으로 나눠지는 수이므로 1 제외하고 2는 짝수만 나뉘므로 2 제외하고
void fourth(); // 검사중 나뉘어 지는 수의 개수가 2개 이상이면 다음 숫자로 패스
void fifth();  // 중간에 나누어 떨어지는 수가 자기 자신이 아니면 다음 숫자로 패스
void sixth();  // 짝수로 나뉘는 값은 짝수이기 때문에 나누는 수를 홀수로 증가

int main()
{
	double StartTime, EndTime;
	double time1, time2, time3, time4, time5, time6;

	StartTime = clock();
	first();
	EndTime = clock();
	time1 = (EndTime - StartTime) / CLOCKS_PER_SEC;
	printf("first time : %.3lf\n", time1);

	StartTime = clock();
	second();
	EndTime = clock();
	time2 = (EndTime - StartTime) / CLOCKS_PER_SEC;
	printf("second time : %.3lf\n", time2);

	StartTime = clock();
	third();
	EndTime = clock();
	time3 = (EndTime - StartTime) / CLOCKS_PER_SEC;
	printf("third time : %.3lf\n", time3);

	StartTime = clock();
	fourth();
	EndTime = clock();
	time4 = (EndTime - StartTime) / CLOCKS_PER_SEC;
	printf("fourth time : %.3lf\n", time4);

	StartTime = clock();
	fifth();
	EndTime = clock();
	time5 = (EndTime - StartTime) / CLOCKS_PER_SEC;
	printf("fifth time : %.3lf\n", time5);

	StartTime = clock();
	sixth();
	EndTime = clock();
	time6 = (EndTime - StartTime) / CLOCKS_PER_SEC;
	printf("sixth time : %.3lf\n", time6);

	return 0;
}

 

void first()
{
	int no = 1;
	FILE *fp = NULL;

	fp = fopen("first.txt", "w");

	for (int i = 2; i <= TEMP; i++)
	{
		int cnt = 0;

		for (int j = 1; j <= i; j++)
		{
			if ((i % j) == 0)
			{
				cnt++;
			}
		}
		
		// if(cnt == 2)
		//{
		//	printf("first 소수 : %-10d개수 : %d\n", i, no++);
		// }

		if (cnt == 2)
		{
			fprintf(fp, "소수 : %-10d개수 : %d\n", i, no++);
		}
	}

	fclose(fp);
}

 

void second()
{
	int no = 1;
	FILE *fp = NULL;

	fp = fopen("second.txt", "w");

	fprintf(fp, "소수 : %-10d개수 : %d\n", 2, no++);

	for (int i = 3; i <= TEMP; i += 2)
	{
		int cnt = 0;

		for (int j = 1; j <= i; j++)
		{
			if ((i % j) == 0)
			{
				cnt++;
			}
		}

		// if(cnt == 2)
		//{
		//	printf("second 소수 : %-10d개수 : %d\n", i, no++);
		// }

		if (cnt == 2)
		{
			fprintf(fp, "소수 : %-10d개수 : %d\n", i, no++);
		}
	}
	
	fclose(fp);
}

 

void third()
{
	int no = 1;
	FILE *fp = NULL;

	fp = fopen("third.txt", "w");

	fprintf(fp, "소수 : %-10d개수 : %d\n", 2, no++);

	for (int i = 3; i <= TEMP; i += 2)
	{
		int cnt = 0;

		for (int j = 3; j <= i; j++)
		{
			if ((i % j) == 0)
			{
				cnt++;
			}
		}

		// if(cnt == 1)
		//{
		//	printf("third 소수 : %-10d개수 : %d\n", i, no++);
		// }

		if (cnt == 1)
		{
			fprintf(fp, "소수 : %-10d개수 : %d\n", i, no++);
		}
	}
	
	fclose(fp);
}

 

void fourth()
{
	int no = 1;
	FILE *fp = NULL;

	fp = fopen("fourth.txt", "w");

	fprintf(fp, "소수 : %-10d개수 : %d\n", 2, no++);

	for (int i = 3; i <= TEMP; i += 2)
	{
		int cnt = 0;

		for (int j = 3; j <= i; j++)
		{
			if ((i % j) == 0)
			{
				cnt++;

				if (cnt >= 2)
				{
					break;
					;
				}
			}
		}

		// if(cnt == 1)
		//{
		//	printf("fourth 소수 : %-4d개수 : %d\n", i, no++);
		// }

		if (cnt == 1)
		{
			fprintf(fp, "소수 : %-10d개수 : %d\n", i, no++);
		}
	}
	
	fclose(fp);
}

 

void fifth()
{
	int no = 1;
	FILE *fp = NULL;

	fp = fopen("fifth.txt", "w");

	fprintf(fp, "소수 : %-10d개수 : %d\n", 2, no++);

	for (int i = 3; i <= TEMP; i += 2)
	{
		for (int j = 3; j <= i; j++)
		{
			if ((i % j) == 0)
			{
				if (i != j)
				{
					break;
				}
				// else
				//{
				//	printf("fifth 소수 : %-10d개수 : %d\n", i, no++);
				// }
				else
				{
					fprintf(fp, "소수 : %-10d개수 : %d\n", i, no++);
				}
			}
		}
	}
	
	fclose(fp);
}

 

void sixth()
{
	int no = 1;
	FILE *fp = NULL;

	fp = fopen("sixth.txt", "w");

	fprintf(fp, "소수 : %-10d개수 : %d\n", 2, no++);

	for (int i = 3; i <= TEMP; i += 2)
	{
		for (int j = 3; j <= i; j += 2) // 여기서 i까지가 아니라 sqrt(i) 까지 해서 하는 방법도 있음
		{
			if ((i % j) == 0)
			{
				if (i != j)
				{
					break;
				}
				// else
				//{
				//	printf("sixth 소수 : %-10d개수 : %d\n", i, no++);
				// }
				else
				{
					fprintf(fp, "소수 : %-10d개수 : %d\n", i, no++);
				}
			}
		}
	}
	
	fclose(fp);
}