소수 구하기 2

개요

입력받은 수까지 모든 소수를 구하고 출력하라. 에라토스테네스의 체의 방법 - 2의 배수를 소수에서 제외, 3의 배수를 소수에서 제외.... 즉 소수의 배수를 소수에서 제외해서 소수를 구하는 방법

---

Code

#include<stdio.h>
#include<stdlib.h>

void FindPrimeNumber(int* pArray, int index,int L_num)
{
	int i = index;	
	while (i+index<=L_num) {
		i+=index;
		if (pArray[i] == 0) continue;
		else pArray[i] = 0;
	}
}

int main(void)
{
	int* pPrime = NULL;
	int iNum = 0,cnt=0;

	printf("Input Num :");
	scanf_s("%d", &iNum);
	pPrime = (int*)malloc((unsigned)sizeof(int*) * iNum);

	for (int i =2 ; i<=iNum;i++){
		pPrime[0] = 1;
	}
	for (int i = 2; i <= iNum; i++) {
		FindPrimeNumber(pPrime, i,iNum);
	}
	for (int i = 2; i <= iNum; i++) {
		if (pPrime[i] != 0) {
			printf("%3d번째 소수 : %3d\t",cnt+1,i);
			if ((cnt + 1) % 5 == 0) {
				printf("\n");
			}
			cnt++;
		}
	}
	free(pPrime);
	return 0;
}

---

Output