[C언어] 백준 1978 소수찾기

소수인지 확인해야 할 수를 n이라고 할 때, 2부터 (n-1)까지의 수가 n의 약수인지 아닌지를 %를 통해 확인하면 된다.

 

 

풀이1

반복문의 사용이 불가피하다고 생각되어 반복을 조금이라도 줄이려고 3부터 n-1까지 홀수만을 체크했다.

 

n = 1일때는 소수가 아니고

n = 2일때는 소수이고

n > 2일때는 3이상의 홀수의 배수인지를 루프를 통해 체크하는 방식인데,

코드를 가능한 단순화했더니 직관적이지 못하다.

실제로도 코드를 줄이려고 한 후  계속 디버그를 해야했다.

#include <stdio.h>

int main(void)
{
	int N, n, cnt = 0, i, isPrime;
	scanf("%d", &N);
	while (N--)
	{
		scanf("%d", &n);
		if (isPrime = n > 1 && (n % 2 || n==2)) // n이 1보다 크고, 2이거나 홀수일 때 isPrime = TRUE
			for (i = 3; i < n && (isPrime = n % i); i += 2); // n=1,2,3일땐 루프 바로 나옴
		if (isPrime)
			cnt++;
	}
	printf("%d", cnt);

	return 0;
}

 

원코드

#include <stdio.h>

int main(void)
{
	int N, n, cnt = 0, i, isPrime;
	scanf("%d", &N);
	while(N--)
	{
		scanf("%d", &n);
		isPrime = 1;
		if(n == 1) isPrime = 0;
		else
		{
			if (n != 2 && n % 2 == 0) isPrime = 0;
			else
				for (i = 3; isPrime && i < n; i += 2)
					if (n % i == 0)	isPrime = 0;
		}
		if (isPrime) cnt++;
	}
	printf("%d", cnt);

	return 0;
}

 

풀이2

97같은 수가 왔을 때를 대비해 반복횟수를 굳이 줄이려고 하지 않고,

2부터 n-1까지의 수를 짝수,홀수 할 것 없이 모두 체크한다면 코드는 좀 더 알아보기 쉬워진다.

#include <stdio.h>

int main(void)
{
	int N, n, cnt = 0, i;
	scanf("%d", &N);
	while(N--)
	{
		scanf("%d", &n);
		for (i = 2; i < n && n % i; i++);
		cnt += (n == i);
	}
	printf("%d", cnt);

	return 0;
}