[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