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

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <math.h>

int isPrimeNumber(int x);			//소수 판별 함수 선언
int main() {
	int N, M;

	scanf("%d%d", &M, &N);
	for (int i = M; i <= N; i++) {
		if (isPrimeNumber(i) > 0) {
			printf("%d\n", isPrimeNumber(i));
		}
	}
}


int isPrimeNumber(int x) {
	int length, i = 2;
	length = sqrt(x);
	if (length == sqrt(x)) return 0;		//1을 배제하자
	while(i <= length) {
		if (x % i == 0) {return 0;}
		i += i % 2 ? 2 : 1;		//2를 제외한 짝수는 소수가 될 수 없다.
	}
	return x;
}

1978번 소수 찾기와 2581번 소수문제를 선행하였다면 쉽게 풀 수 있는 문제였다.

아르키메데스의 체의 원리를 이용하여 양의 제곱근로 판별 범위를 설정하였고

판별 과정에서 2를 제외한 짝수는 소수가 될 수 없기 때문에 배제하였다.

 

그럼에도 불구하고 168ms라는 시간이 걸렸는데 대다수 맞힌 사람이 12ms인 것을 감안하면 0.1초가 넘게 차이났다.

#include <stdio.h>
int main(void){
    int M, N;
    scanf("%d%d", &M, &N);
    
    //인덱스 0~1,000,000까지의 자연수 배열 만들기 + 0으로 초기화해서 모두 소수라고 가정
    char num[1000001]={0, };
    num[1]=1;                 //1은 소수 아님, 2와 3은 소수임
    
    //num[4]~num[1000000]까지 소수면 0 그대로, 소수가 아니면 1
    //2*2, 2*3, 2*4 ... 1000*999, 1000*1000 ... 은 모두 나눠지므로 소수가 아님을 이용한 방식
    for (int i=2; i<=1000; i++) {     //i=2~1000, j=2~1000, i*j<=1,000,000
        if (num[i]==0)    //이미 num[i]를 1로 바꾼 것들은 검사 안 함
            for (int j = 2; i * j <= 1000000; j++)
                num[i*j] = 1;
    }
    for (int i=M; i<=N; i++) {
        if (num[i]==0)    //num[i]가 0이면 소수
            printf("%d\n", i);
        }
    
    return 0;
} minwachya님의 코드

12ms를 기록한 코드이다. 0으로 초기화하여 0이 아닌것과 구분하여 출력하는 아이디어는 정말 자주 쓰이는 것 같다.

내 코드와 반복문 개수와 범위에서 큰 차이가 없는 것 같은데 시간 차이는 함수의 호출 때문일까?

혹시 보시는 분 중에 아시는 분이 계시다면 댓글 달아주시면 감사하겠습니다.

저도 계속 찾아보겠습니다.