Wechall - Prim Factory 정리

이번 문제의 목표는 소수를 찾는 것입니다.

 

하지만 조건이 2개 있는데요

 

첫번째는 1000000 (백만) 이상의 숫자부터 찾는 것과

 

두번째는 각 자리수의 합이 소수인 것 입니다.

 

 

자리수가 크기 때문에 손으로 계산하기엔 무리라 생각하여 코딩을 하였습니다.

 

파이썬으로 해도 되지만 오랜만에 C로 코딩을 해보았습니다.

 

#include <stdio.h>
#include <time.h>
#include <math.h>
#pragma warning(disable : 4996)

// 소수 판별
int isprime(int number) {
	if (number == 4) {
		return false;
	}
	for (int i = 2; i<int(sqrt(number)); i++) {
		if (number%i == 0) {
			return false;
		}
	}
	return true;
}

int main() {
	clock_t start, end;
	int num = 0;
	int count = 0;
	start = clock();

	while (1) {
		// 시작 값은 백만
		for (int i = 1000000;; i++) {			
			// 1차 소수 판별 
			if (isprime(i)) {
				// 각 자리수 합 소수 판별
				int tmp = i;
				int sum = 0;
				while (tmp != 0) {
					sum += (tmp % 10);
					tmp /= 10;
				}
				if (isprime(sum)) {
					printf("%d", i);
					count++;

					// 2개 찾기
					if (count == 2) {

						end = clock();

						float res = (float)(end - start) / CLOCKS_PER_SEC;
						printf("\n걸린시간 >> %f", res);

						return 0;
					}
				}
			}
		}
	}
}

 

출력결과는 다음과 같습니다.

 

10000331000037 
걸린시간 >> 0.004000

 

작업시간은 오래 걸리지 않았습니다.

 

이번문제의 정답은 10000331000037 였습니다.