JAVA 백준 19741번 Patterns

문제

Inspired by the Ulam spiral, which unravels strange patterns of prime numbers' distribution, Petya decided to come up with his own analog.
Petya writes down integers from
$1$ to $n^2$ into square table of size $n\times n$ starting from the upper left corner. Numbers from $1$ to $n$ go into the first row, numbers from $n + 1$ to
$2n$ --- into the second row, and so on.
Then he colors cells which contain the number with no more than
$k$ different divisors. After that, Petya studies the resulting picture in hope of finding some patterns. For example, if $n = 7$,
$k = 3$, Petya will get the following picture:

Help Petya, print the picture which he will get after coloring, representing colored cells with asterisks <<*>>, and non-colored cells with dots <<.>>.

입력

Input contains two integers n$n$ and k$k$ (1≤n≤40$1 \le n \le 40$, 1≤k≤n2$1 \le k \le n^2$).

7 3

출력

Output n$n$ lines, each one containing n$n$ characters. If the j$j$-th cell of i$i$-th row of Petya's table is colored, then j$j$-th character of i$i$-th line should be equal to <<*>>, and <<.>> otherwise.

*****.*
.*.*.*.
..*.*..
.*.*...
*.*....
.*...*.
*...*.*

알고리즘 분류

브루트포스 알고리즘(bruteforcing), 구현(implementation), 수학(math), 정수론(number_theory), 소수 판정

소스코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int[] divisors = new int[N * N + 1];
        for (int i = 2; i <= N * N; i++) {
            for (int j = i; j < divisors.length; j += i) {
                divisors[j]++;
            }
        }
        for (int i = 1; i <= N * N; i++) {
            if (divisors[i] < K) {
                bw.write("*");
            } else {
                bw.write(".");
            }
            if (i % N == 0)
                bw.newLine();
        }
        bw.flush();
    }
}