[예제] 에라토스테네스의 체로 소수 찾기

int main()
{
	int num,i=0,j,n;
	printf("숫자를 입력하세요 : ");
	scanf("%d", &num);

	int* nArr = (int*)malloc(sizeof(int) * num);
	
	/*while (i < num) // 아레토스테네스의 체를 사용하지 않는 로직
	{
		nArr[i] = 1;

		if (((i + 1) % 2 == 0) && ((i+1) != 2))
			nArr[i] = 0;
		else if (((i + 1) % 3 == 0) && ((i+1) != 3))
			nArr[i] = 0;
		else if (((i + 1) % 5 == 0) && ((i+1) != 5))
			nArr[i] = 0;
		else if (((i + 1) % 7 == 0) && ((i+1) != 7))
			nArr[i] = 0;

		if (nArr[i] == 1 && i !=0)
			printf("%d\n", i + 1);

		i++;
	}*/

	for (i = 2; i < num; i++)
	{
		nArr[i] = 1;
	}

	for (i = 2; i < num; i++)
	{
		for (j = 2, n = i * j; n < num; n = ++j * i)
			nArr[n] = 0;
	}

	for (i = 2; i < num; i++)
	{
		if (nArr[i] == 1)
			printf("%d\n", i);
	}

	free(nArr);
}