Submission #2461986
Source Code Expand
import java.util.Arrays; public class Main { private static void solve() { int n = ni(); int[] primes = sieveAtkin(55555); for (int p : primes) { if (p % 5 == 1) { n --; out.print(p + " "); if (n == 0) break; } } out.println(); } public static int[] sieveAtkin(int size) { boolean[] isPrime = new boolean[size + 1]; int sqrtN = (int) Math.sqrt(size); int n; for (int x = 1; x <= sqrtN; ++x) { for (int y = 1; y <= sqrtN; ++y) { n = 4 * x * x + y * y; if (n <= size && (n % 12 == 1 || n % 12 == 5)) { isPrime[n] = !isPrime[n]; } n = 3 * x * x + y * y; if (n <= size && n % 12 == 7) { isPrime[n] = !isPrime[n]; } n = 3 * x * x - y * y; if (x > y && n <= size && n % 12 == 11) { isPrime[n] = !isPrime[n]; } } } for (n = 5; n <= sqrtN; ++n) { if (isPrime[n]) { for (int k = n * n; k <= size; k += n * n) { isPrime[k] = false; } } } isPrime[2] = isPrime[3] = true; int[] ret = new int[size]; int count = 0; for (int i = 1; i < size; i++) { if (isPrime[i]) { ret[count++] = i; } } return Arrays.copyOf(ret, count); } public static void main(String[] args) { new Thread(null, new Runnable() { @Override public void run() { long start = System.currentTimeMillis(); String debug = args.length > 0 ? args[0] : null; if (debug != null) { try { is = java.nio.file.Files.newInputStream(java.nio.file.Paths.get(debug)); } catch (Exception e) { throw new RuntimeException(e); } } reader = new java.io.BufferedReader(new java.io.InputStreamReader(is), 32768); solve(); out.flush(); tr((System.currentTimeMillis() - start) + "ms"); } }, "", 64000000).start(); } private static java.io.InputStream is = System.in; private static java.io.PrintWriter out = new java.io.PrintWriter(System.out); private static java.util.StringTokenizer tokenizer = null; private static java.io.BufferedReader reader; public static String next() { while (tokenizer == null || !tokenizer.hasMoreTokens()) { try { tokenizer = new java.util.StringTokenizer(reader.readLine()); } catch (Exception e) { throw new RuntimeException(e); } } return tokenizer.nextToken(); } private static double nd() { return Double.parseDouble(next()); } private static long nl() { return Long.parseLong(next()); } private static int[] na(int n) { int[] a = new int[n]; for (int i = 0; i < n; i++) a[i] = ni(); return a; } private static char[] ns() { return next().toCharArray(); } private static long[] nal(int n) { long[] a = new long[n]; for (int i = 0; i < n; i++) a[i] = nl(); return a; } private static int[][] ntable(int n, int m) { int[][] table = new int[n][m]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { table[i][j] = ni(); } } return table; } private static int[][] nlist(int n, int m) { int[][] table = new int[m][n]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { table[j][i] = ni(); } } return table; } private static int ni() { return Integer.parseInt(next()); } private static void tr(Object... o) { if (is != System.in) System.out.println(java.util.Arrays.deepToString(o)); } }
Submission Info
Submission Time | |
---|---|
Task | D - Five, Five Everywhere |
User | hiromi_ayase |
Language | Java8 (OpenJDK 1.8.0) |
Score | 400 |
Code Size | 3805 Byte |
Status | AC |
Exec Time | 78 ms |
Memory | 21460 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 400 / 400 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt, sample_03.txt |
All | in01.txt, in02.txt, sample_01.txt, sample_02.txt, sample_03.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
in01.txt | AC | 77 ms | 21460 KB |
in02.txt | AC | 77 ms | 19600 KB |
sample_01.txt | AC | 77 ms | 20180 KB |
sample_02.txt | AC | 78 ms | 21076 KB |
sample_03.txt | AC | 75 ms | 19796 KB |