[SWEA] 4698. 테네스의 특별한 소수

 

https://swexpertacademy.com/main/solvingProblem/solvingProblem.do

SW Expert Academy

---

접근 방법

소수는 1과 자신 외의 약수는 가지지 않는 1 보다 큰 자연수이다.

처음에는 시간 복잡도가 O(N^2)인 완전 탐색을 썼는데 큰 수가 입력되자 시간이 초과됐다.

해결책을 알아보던 중 시간 복잡도가 O(Nlog(logN))인 에라토스테네스의 체 소수 판별 알고리즘을 접하게 됐다.

 

참고 영상 : https://ko.khanacademy.org/computing/computer-science/cryptography/comp-number-theory/v/sieve-of-eratosthenes-prime-adventure-part-4

에라토스테네스의 체 (동영상) | 소수 판별법 | Khan Academy

DP처럼 하나의 check 배열을 만들고

2부터 check 되지 않은 수의 배수들을 check 하며 제거해 나가는 방식이다.

이때 시작 값을 제거해서는 안 된다. 그래서 다음 for문은 이전 for문 값의 2 배수부터 반복 계산한다.

이후 check 되지 않은 수들을 탐색하며 셌다.

속도가 빠른 대신 메모리 공간이 꽤 필요했다.

 

소스 코드

import java.util.*;

class Solution {
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for(int t=1; t<=T; t++) {
            int D = sc.nextInt();
        	int N = sc.nextInt();
            int L = sc.nextInt();
            int cnt = 0;
            
            int[] check = new int[L+1];
                      
            for(int i=2; i<=L; i++) {
            	if(check[i] == 1) continue;
            	for(int j=i*2; j<=L; j+=i) {
            		check[j] = 1;
            	}
            }
            
            for(int i=N; i<=L; i++) {
            	if(i == 1) continue;
            	if(check[i] == 0 && (i+"").contains(D+""))
            		cnt += 1;
            }
            
            System.out.println("#" + t + " " + cnt);
        }
    }
}