BOJ 1929 소수 구하기

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

---

그냥 전 문제와 똑같이 풀었다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

#include<stdio.h> #define FOR(i,j) for(int i=0;i<j;i++) void isprime(int x); int main() { int M, N; scanf("%d %d", &M, &N); for (;M <= N;M++) { isprime(M); } return 0; } void isprime(int x) { int flag = 0; for (int i = 2;i <= x;i++) { if (x%i == 0) flag++; } if (flag == 1) printf("%d\n", x); }

그랬더니 시간 초과가 떴다. 따라서 다른 방법^[각주:1]으로 풀어야 한다.

크게 어려운 방법은 아니니 그냥 그대로 짜면 된다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

#include<stdio.h> #include<malloc.h> #define MAX 1000001 int main() { int *num = calloc(MAX, sizeof(int)); int M, N; scanf("%d %d", &M, &N); num[1] = -1; for (int i = 2;(i*i) <= N;i++) { for (int j = 2;j <= (N / i);j++) { num[i*j] = -1; } } for (int i = M;i <= N;i++) { if (num[i] == 0) printf("%d\n", i); } free(num); return 0; }

int로 배열을 선언 했더니 오버플로우가 떠서 동적할당해버렸다.

어차피 0으로 초기화해서 사용할 거니깐 그냥 calloc으로 동적할당 시켰다.

i는 23456식으로 증가하는 변수이고 j는 i의 배수들을 뜻한다.

처음부터 끝까지 다 돌 필요 없이 적당히 돌려주면 된다.

어떤 수의 배수들^[각주:2]은 배열에서 -1로 설정하고 반복문이 끝난 이후 0인 숫자들만 출력하면 된다.

글 작성하면서 든 생각인데 num[i]가 이미 -1인 경우에는 굳이 더 볼 필요 없어보인다.

1. 에라토스테네스의 체 [본문으로]
2. i * j [본문으로]