[SW Expert Academy] 테네스의 특별한 소수 (D3)

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AWRuoqCKkE0DFAXt&categoryId=AWRuoqCKkE0DFAXt&categoryType=CODE&problemTitle=&orderBy=PASS_RATE&selectCodeLang=ALL&select-1=3&pageSize=10&pageIndex=13

SW Expert Academy

import java.util.Scanner;

class Solution {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();

		boolean isPrime[] = new boolean[1000001];

		for (int i = 0; i < isPrime.length; i++) {
			isPrime[i] = true;
		}

		isPrime[0] = isPrime[1] = false;

		for (int i = 2; i <= Math.sqrt(isPrime.length); i++) {
			if (isPrime[i])
				for (int j = i*i; j < isPrime.length; j += i) {
					isPrime[j] = false;
				}
		}

		for (int tc = 1; tc <= t; tc++) {
			int d = sc.nextInt();
			int a = sc.nextInt();
			int b = sc.nextInt();

			int cnt = 0;
			String num = String.valueOf(d);

			for (int i = a; i <= b; i++) {
				if (isPrime[i] && String.valueOf(i).contains(num)) {
					cnt++;
				}
			}
			System.out.println("#"+tc+" "+cnt);
		}

	}
}

 

에라토스테네스의 체 애니메이션을 위키백과에서 가져왔다.

시간복잡도: O(Nlog(logN))

 

https://olrlobt.tistory.com/61

[Java] Integer.toString()와 String.valueOf()의 차이