【코딩】 C 언어로 n 이하의 소수, 에라토스테네스의 체

C 언어로 n 이하의 소수, 에라토스테네스의 체

 

추천글 : 【C 언어】 C 언어 목차

---

 

#include <stdio.h>
#include <stdlib.h>
/* This source is for finding all the primes between 1 and n with Erathosthenes' sieve*/

int main(int argc, char *argv[]) {
	int n, m;
	scanf("%d", &n);
	char c[n+1];
	int i, j;
	int count = 0;
	for(i=1; i <= n; i++){
		c[i] = 0; // clean the matrix
	}
	printf("[소수의 종류]\n");
	for(i = 2; i <= n; i++){
		if(c[i] == 0){ // "=" if i is one of primes,
			printf("%d ", i);
			m = n / i;
			for(j = 1; j <= m; j++) c[j*i] = 1; // mark i's multiples as composite number
			count ++;
		}
	}
	printf("\n\n[소수의 개수]\n%d개", count);
	return 0;
}

 

입력 : 2016.02.09 20:52