[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을 사용하면 간편하게 풀 수 있을 것이다.
Author And Source
이 문제에 관하여([C언어] 백준 1929 : 소수 구하기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kimmainsain/C언어-백준-1929-소수-구하기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)