정올 - C 2813번 수학2 - 소수의 개수

문제 : http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2079&sca=2040

JUNGOL

문제

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

 

[그림1] 입 출력 형식

 

[그림2] 입 출력 예제

# include <stdio.h>

int p[2000005];

void prime(int num)
{
	int i,j;
	
	p[0]=p[1]=1;
	
	for(i = 2; i<=num/i; i++)
	{
		if(p[i] == 0)
		{
			for(j = i*i; j<=num; j+=i)
			{
				p[j] = 1;
			}
		}
	}
}


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

	
	return 0;
}