[Algorithm] 소수의 개수 구하기

배열 A[99]에 2~100 사이의 정수를 기억시킨 후 이 배열을 이용하여 소수의 개수를 구하시오.

배열에 들어있는 연속된 숫자의 소수 여부를 판별하기 위해서는 정수의 수열에서 처음 나온 소수의 배수들은 소수가 아니라는 원리를 이용합니다. 배열의 첫번째에 들어있는 2는 소수이지만 2의 배수들은 모두 소수가 아닙니다. 그러므로 2의 배수가 들어 있는 위치에는 모두 0을 채워 소수가 아님을 표시합니다. 소수의 판별은 배열의 해당 위치에 0이 들어 있는지만 확인하면 됩니다.

 

걸러내기

 

C언어 / C++ 코드

#include<stdio.h>
main()
{
	int k,i,j,m;
	int a[99];
	
	k=1;
	do{ //배열 a에 값을 입력한다. 
		k++;
		a[k-2] = k; 
	}while(k<101);
	
	j=0;
	i=-1;
	 
	
	while(1){
		i++;
		if(i>98){
			printf("%d번쨰까지의 소수의 갯수 = %d",i+1,j);
			break;
		}
		
		if(a[i]==0){ 
			continue;
		}
		
		j++;
		m=i;
		
		while(1){ 
			m+=a[i];
			if(m>98)
				break;
			a[m] = 0;
		}
	}
	
}

결과

 

댓글

Designed by JB FACTORY