2813 : 소수의 개수

문제

소수(prime number)란 1보다 큰 자연수 중 1과 자기 자신 두 개만을 약수로 갖는 수를 말한다.
자연수 M과 N을 입력받아 M부터 N까지 소수의 개수를 구하여 출력하는 프로그램을 작성하시오.

 

입력형식

자연수 M과 N이 공백으로 구분되어 주어진다. (1 ≤ M ≤ N ≤ 2,000,000)

 

출력형식

M이상 N이하의 자연수 중 소수가 몇 개인지 구하여 출력한다.

 

<코드>

#include <stdio.h>
 
 int prime[2000005];
 
void eratos(int n)
{
    int i, j;
	
	prime[0] = prime[1] = 1;
    for (i=2; i*i <= n; i++)
    {
        if (!prime[i])
        {
            for (j=i*i; j<=n; j+=i) // i의 제곱부터 n까지 i씩 증가
            {
                prime[j] = 1; // i의 배수 제거하기
            }
        }
    }
}

int main()
{
    int s, e, i;
    int cnt = 0;
    scanf("%d %d", &s, &e);
    
    eratos(e);
    
    for (i=s; i <= e; i++)
    {
        if(prime[i]==0)
            cnt++;
    }
    printf("%d\n", cnt);
    return 0;
}