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

생각의 흐름

별 생각 없었음 그냥 전에 소수 구한 방법 조금 수정해서 제출하고 안되면 조금 더 생각해보자 이정도 생각한듯?

맨 처음 제출한 코드 (시간 초과)

#include <stdio.h>

int main()
{
    int a, b, i;
    scanf("%d %d", &a, &b);
    while (a <= b)
    {
        if (a >= 2)
        {
            int i = 2;
            while (i <= a)
            {
                if (i == a)
                {
                    printf("%d\n", a);
                }
                if (a % i == 0)
                    break;
                i++;
            }
        }
        a++;
    }
}

그냥 a값까지 다 돌리면서 소수찾기는 시간초과로 틀렸다.

그래서 예전에 했던 is_prime함수를 사용해보기로 했다.

코드 설명
만약 2부터 100까지 소수체크를 한다고 가정해보자.
2~9까지 판별하고, 10을 판별할 건데 그 이상의 계산은 의미가 없다. 어차피 100 이하의 수만 계산하면 되기 때문이다. 그래서 10을 판별해 100이 소수인지를 체크하고 끝낸다.

수정한 코드

#include <stdio.h>

int ft_is_prime(int nb)
{
	int i;
	i = 2;
	if (nb < 2)
		return (0);
	while (i <= (nb / i))
	{
		if (nb % i == 0)
			return (0);
		i++;
	}
	return (1);
}

int main()
{
	int a, b;
	scanf("%d %d", &a, &b);
	while (a <= b)
	{
		if (ft_is_prime(a) == 1)
			printf("%d\n", a);
		a++;
	}
}

다른 사람 코드

#include <stdio.h>
int main(void){
    int m,n,arr[1000001] = {0,};
    arr[1] = 1;
    
    scanf("%d %d", &m, &n);
    
    for(int i = 2; i <= n; i++){
        for(int j = 2; i * j <= n; j++){
            arr[i*j] = 1;
        }
    }
    
    for(int i = m; i <= n; i++){
        if(arr[i] == 0)
            printf("%d\n",i);
    }
    
    return 0;
}

에라토스테네스의 체

위의 그림을 보면 이해가 쉽다. 2가 들어왔으면, 4, 6, 8, 10 .. 이런식으로 그 소수는 소수가 아니고, 3이 들어왔으면 6, 9, 12 .. 이런식으로 소수가 아니다. 이는 nested loop을 사용하면 간편하게 풀 수 있을 것이다.

출처 https://velog.io/@usoab0561/%EB%B0%B1%EC%A4%80-1929%EB%B2%88-%EC%86%8C%EC%88%98%EA%B5%AC%ED%95%98%EA%B8%B0-%EC%84%B1%EA%B3%B5