[C언어] 백준 1929번 소수구하기

 

[풀이1]

1112KB 108MS

 

여태 소수 관련 문제를 풀어왔던 대로 풀어봤다.

m > 1보다 크고, 2이거나 2의 배수가 아닐 때 for loop을 통해

n까지 홀수로 증가하는 m이 소수인지 아닌지를 판별해 소수일 경우에만 m을 출력한다.

 

조건  체크와 할당식을 너무 많이 써서 그런가 속도가 잘 나오지 않았다.

그렇다고 m을 증가할 때 조건 체크없이 m++한다면 더 오랜 시간이 걸린다.

 

#include <stdio.h>

int main(void)
{
	int m, n, i, isPrime;
	scanf("%d %d", &m, &n);
	while (m < n + 1)
	{
		if (isPrime = (m > 1 && (m == 2 || m % 2)))
		{
			for (i=3; i * i < m + 1 && (isPrime = m % i); i+=2);
			if (isPrime) printf("%d\n", m);
		}
		m == 1 ? m++ : (m % 2) ? m+=2 : m++;
	}

	return 0;
}

 

 

 

 

 

[풀이2]

1968KB 12MS

어떻게 해야 실행 시간을 줄일 수 있을까 사람들 코드를 참고했더니 특정 풀이법이 있는 듯하다.

에라토스테네스의 체를 이용한다.

2부터 n까지의 숫자 중, 소수를 찾을 때마다 소수의 배수를 모두 지우는 방법이다.

 

• 배열을 초기화할 때 기본값은 0 이므로 소수의 배수를 지울때마다 1로 값을 수정하고 마지막에 값이 1이 아닌 모든 요소들을 출력한다.
  • 따라서 소수일 때 0, 소수가 아닐 때 1로 nums는 0과 1 두 가지 작은 정수값만을 저장할 것이기 때문에 int가 아닌 char로 선언한다.
• 보통 배열을 다룰 때 0열에 첫 값 1을 저장하곤 하지만, 여기서는 연산을 줄이기 위해 1열부터 자연수를 차례로 저장할 것이다.
• 첫번째 loop의 조건이 i * i < n+1이 될 수 있는 이유는,
  i가 n의 제곱근을 초과하는 구간부터는 소수를 찾기 위한 과정에서 n의 약수로서 의미가 없기 때문이다.
  
  • Ex. 2~26까지의 소수를 판별하기 위해 2~26을 돌면서 배수들을 지우기로 한다.
    2 4 6 8 10 12 14 16 18 20 22 24 26
    3 6 9 12 15 18 21 24
    4 8 12 16 20 24
    5 10 15 25
    6 12(6*2) 18(6*3) 24(6*4)
    7 14(7*2) 21(7*3)
    8 16(8*2) 24(8*3)
    9 18(9*2)
    10 20(10*2)
    11 22(11*2)
    12 24(12*2)
    13 26(13*2)
  •  제곱근을 기점으로 필연적으로 이를 초과하는 값들의 배수는 이미 나온 수의 배수들이다.
    

    

• if(!nums[i])
  • nums[i]값이 이미 소수가 아니라면, 그 배수들 또한 이미 배제되었을 것이다.
    ex. 4의 배수들은 2의 배수들을 제외시킬 때 이미 제외되었다.
  • 따라서 연산을 조금이라도 줄이기 위해 if문을 넣어줬다
• for(j=i*i; i <n+1; j+=i)
       nums[j] =1;
  • j = 2*i로 초기화하는 사람도 있고 아니면 j=1부터 시작해 nums[i*j]로 두는 사람도 있는듯하다.
  • j = i * i로 초기화한 이유는 i의 제곱 이전까지 ( 인덱스 1 * i, 2 * i, ... i * i-1)의 요소들은
    이미 이전의 for loop에 의해 소거되었기 때문
    ex. i = 4일때 인덱스 8, 12는 i=2, i=3에 의해 루프를 돌면서 이미 소거되었다.
  • 새로운 값을 할당할 인덱스를 찾기 위해 i*j 곱하기 연산을 하고 싶지 않아 j를 애초에 i*i로 초기화하고 i만큼 증가시킨다.

 

#include <stdio.h>

int main()
{
	int m, n, i, j;
	char nums[1000001] = {1, 1}; //0, 1
	scanf("%d %d", &m, &n);

	for (i = 2; i * i < n + 1; i++) 
		if(!nums[i])
			for (j = i * i; j < n+1; j += i)
				nums[j] = 1;

	for (i = m; i < n + 1; i++)
		if (!nums[i]) printf("%d\n", i);

	return 0;
}