[알고리즘 문제] 접두 소수

티바이트 2016. 10. 26. 00:49

2016. 10. 26. 00:49

출처

Koreatech OnlineJudge (링크)

문제이해

소수 719333은 큰 자리부터 순서대로 붙여 나간 각각의 수

7, 71, 719, 7193, 71933이 모두 소수이다.

문제에서 이러한 수를 '접두 소수'라고 정의한다.

수의 길이 n이 주어졌을 때 n자리인 접두 소수를 출력하는 문제이다.

문제접근

우선 소수를 판별하는 함수를 작성해야 한다.

n이 소수인지 판별할 때 2부터 n까지 나눠봐서

나누어 떨어지는 경우가 있으면 소수가 아니고, 없으면 소수이다.

그런데 이렇게 하면 n이 커지는 경우 연산량이 비례해서 늘어나므로 연산량을 줄여야 한다.

약수는 대칭성이 있기 때문에 sqrt(n)까지만 나눠봐도 소수를 판별할 수 있다.

다음은 n자리의 접두소수를 백트래킹(Backtracking)으로 구해야 하는데,

한 자리 소수인 2, 3, 5, 7부터 시작하여 다음 자리수를 검사한다.

3부터 시작하는 경우 다음 자리는 짝수와 5의 배수를 제외한

31, 33, 37, 39를 소수판별하면 되는 것이다.

구현

재귀함수나 스택, 큐 등을 사용하여 구현할 수 있다.

main()함수 내에서 다음과 같이 2, 3, 5, 7와 전체 자리수를 주어 시작하고,

print(2, digit);

print(3, digit);

print(5, digit);

print(7, digit);

print()함수 내에서는 digit이 1이 되었을 때 탈출하면서 출력을 하도록 조건을 주었다.

그리고 아래와 같이 다음 자리에 해당하는 재귀호출을 한다.

n *= 10;

for (int i = 1; i < 10; i += 2) {

if (i == 5) continue;

if (isPrime(n + i)) {

print(n + i, digit-1);

}

실행결과

코드

티바이트