내일은 알고리즘

https://school.programmers.co.kr/learn/courses/30/lessons/12921

에라토스테네스의 체에 대한 지식이 있다면 쉽게 풀리는 문제입니다.

우리가 찾아야 하는것은 넓은 범위의 소수입니다. 즉, 천만개의 숫자에 대해 일일히 소수를 판정하지 않고, 소수가 아닌 수를 지워가면 됩니다.

2부터 n까지 숫자를 탐색하면서 이전에 나누어지지 않았다면, 즉 소수라면 answer를 1 더해주고 소수의 배수들을 전부 체크해줍니다. (어떤 소수의 배수라면 소수가 아닙니다. 소수는 1과 자신으로만 나누어진다는 명제의 대우입니다.)

n까지 모두 순회한다면 우리가 목표로 하는 소수의 갯수를 알 수 있습니다.

def solution(n):
    answer = 0
    divided = [False for i in range(n+1)]

    for i in range(2, n + 1):
        if not divided[i]:
            answer += 1
            d = i * 2
            while d <= n:
                divided[d] = True
                d += i

    return answer

https://school.programmers.co.kr/learn/courses/30/lessons/12977

특정 범위의 소수를 구하는 에라토스테네스의 채와 조합을 응용하는 문제입니다.

우선 세가지 수를 뽑아 나올수 있는 합의 범위는 3000입니다.

매번 합을 구해 소수인지 판별하는것 보다 미리 소수를 구해놓고 비교하는게 더 빠릅니다. 특정 범위안의 모든 소수를 구하는 방법으론 에라토스테네스의 채가 있습니다. 이를 활용해서 3000이하의 모든 수에 관해 소수 여부를 미리 구해놓습니다.

다음으론 더할 세가지 수를 뽑습니다. 순서와 상관없이 합을 구하기 때문에 조합을 응용해 구하면 됩니다.

이번 경우에는 뽑아야할 수가 3개로 정해져 있으므로 3중 for문을 사용해도 구현이 가능합니다.

import copy

def solution(nums):

    def sumCombination(combination):
        return combination[0] + combination[1] + combination[2]

    def makeCombination(list, idx, count):
        if(count == 3):
            combinationList.append(copy.deepcopy(list))
            return
        
        for i in range(idx,len(nums)):
            list[count] = nums[i]
            makeCombination(list, i+1, count+1)


    def makePrimeNumber():
        number = [0 for i in range(3_001)]
        number[1] = 1
        for i in range(2,3_001):
            if(number[i] == 0):
                j = i * 2
                while(j < 3_001):
                    number[j] = 1
                    j += i
        return number

    combinationList = []
    primeNumber = makePrimeNumber()
    makeCombination([0]*3, 0, 0)
    answer = 0
    for i in combinationList:
        sum = sumCombination(i)
        if(primeNumber[sum] == 0):
            answer += 1
            
    return answer


nums = [1,2,7,6,4]
print(solution(nums))

def solution(nums):

    def makePrimeNumber():
        number = [0 for i in range(3_001)]
        number[1] = 1
        for i in range(2, 3_001):
            if(number[i] == 0):
                j = i * 2
                while(j < 3_001):
                    number[j] = 1
                    j += i
        return number

    primeNumber = makePrimeNumber()
    answer = 0

    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            for k in range(j+1, len(nums)):
                sum = nums[i] + nums[j] + nums[k]
                if(primeNumber[sum] == 0):
                    answer += 1
            
    return answer


nums = [1,2,7,6,4]
print(solution(nums))

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWRuoqCKkE0DFAXt 

넓은 범위의 소수를 모두 구하는 '에라토스테네스의 채'를 응용한 문제입니다.

에라토스테네스의 채를 구현하는 방법을 알면 큰 어려움 없이 풀이할 수 있습니다.

이번 문제처럼 여러번 소수를 사용하는 문제에서도 필요한 범위의 소수를 미리 구해놓고 정답체크를 진행하면 매번 새로 소수를 구하는 것보다 좋은 성능을 얻을 수 있습니다. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class q4698Re_SWEA_테네스의특별한소수 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int T = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();

		int[] arr = new int[1_000_001];

		arr[1] = 1;

		for (int i = 2; i <= 1_000_000; i++) {
			if (arr[i] == 0) {
				for (int j = i * 2; j <= 1_000_000; j += i) {
					arr[j] = 1;
				}
			}
		}

		for (int t = 1; t <= T; t++) {
			st = new StringTokenizer(br.readLine());
			int D = Integer.parseInt(st.nextToken());
			int A = Integer.parseInt(st.nextToken());
			int B = Integer.parseInt(st.nextToken());
			int cnt = 0;

			for (int i = A; i <= B; i++) {
				if (arr[i] == 0) {
					if (String.valueOf(i).contains(String.valueOf(D))) {
						cnt++;
					}
				}
			}

			sb.append("#").append(t).append(" ").append(cnt).append("\n");
		}

		System.out.println(sb);
	}
}