[C\C++] 소수 구하기

자연수 1부터 입력한 수 N까지 소수의 개수 출력하기

자연수 1부터 입력한 수 N까지의 소수의 개수를 출력하는 프로그램을 짠다면 다음과 같다.(sol.1)

#include<stdio.h>

int main() {
	int n = 0,cnt=0,flag;

	scanf("%d", &n);
	for (int i = 2; i <= n; i++) {
		flag = 1;
		for (int j = 2; j < i; j++) {
			if (i % j == 0) {
				flag = 0;
				break;
			}
		}
		if (flag == 1) cnt++;
	}
	printf("%d", cnt);
}

그러나 두번째 for문에서 쓸데없는 연산을 많이 하게 되며 입력한 수가 커질수록 연산은 많아진다.

 

이때, 소수의 특성을 잘 파악하면 연산을 대폭 줄일 수 있다.

 

만일 1부터 42까지의 소수를 확인하고 싶으면 42의 약수를 확인하면 된다.

42	1 * 42
	2 * 21
	3 * 14
	6 * 7

6의 제곱까지만 반복을 하면 다음 값은 이전에 나온 결과랑 동일하기 때문에 연산을 할 필요가 없다.

 

따라서 다음과 같이 나타낼 수 있다.(sol.2)

#include<stdio.h>

int main() {
	int n = 0,cnt=0,flag;

	scanf("%d", &n);
	for (int i = 2; i <= n; i++) {
		flag = 1;
		for (int j = 2; j*j <= i; j++) {
			if (i % j == 0) {
				flag = 0;
				break;
			}
		}
		if (flag == 1) cnt++;
	}
	printf("%d", cnt);
}

 

 

1부터 입력한 숫자N까지의 자리수 개수 구하기

입력한 숫자까지의 각 자리수 개수를 구하기 위해서는 나누기 연산만 이용해 주면 된다.

#include<stdio.h>
using namespace std;

int main() {
	int n = 0, tmp = 0, cnt = 0;

	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		tmp = i;
		while (tmp > 0) {
			tmp = tmp / 10;     //각 자리의 수를 10으로 나눈 몫을 tmp에 대입한다.
			cnt++;     //10으로 전부 나눌 때 까지 연산한다.
		}
	}
	printf("%d", cnt);

	return 0;
}

tmp에 i값을 넣은 다음 tmp를 10으로 나누면 몫이 tmp에 저장되며 몫이 생길 때 마다 cnt가 1씩 증가하게 된다.