#62274 (Java) No.308 素数は通れません

• 問題: No.308 素数は通れません
• ユーザー: uafr_cs
• 提出日時: 2015-12-03 20:14:06
• 言語: Java (openjdk 23)
• 結果: AC
• 実行時間: 146 ms / 1,000 ms
• コード長: 3,430 bytes
• コンパイル時間: 2,057 ms
• コンパイル使用メモリ: 82,056 KB
• 実行使用メモリ: 41,580 KB
• 最終ジャッジ日時: 2024-11-27 18:39:17
• 合計ジャッジ時間: 15,279 ms
• ジャッジサーバーID （参考情報）: judge4 / judge3

ファイルパターン	結果
other	AC * 107

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
import java.math.BigInteger;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.Set;
public class Main {
    
    public static int simulate(final int N){
        boolean[] is_prime = new boolean[N + 1];
        Arrays.fill(is_prime, 2, N + 1, true);
        
        for(int i = 2; i * i <= N; i++){
            if(!is_prime[i]){ continue; }
            
            for(int j = i * 2; j <= N; j += i){
                is_prime[j] = false;
            }
        }
        
        if(is_prime[N]){ return -1; }
        boolean[] visited = new boolean[N];
        for(int mid = 1; mid <= N; mid++){
            Arrays.fill(visited, false);
            
            LinkedList<Integer> queue = new LinkedList<Integer>();
            queue.add(0);
            visited[0] = true;
            while(!queue.isEmpty()){
                final int pos = queue.poll();
                final int number = pos + 1;
                
                if(number == N){ break; }
                //System.out.println(mid + " => " + pos + " : " + (pos % mid));
                
                if(pos % mid > 0 && !is_prime[number - 1] && !visited[pos - 1]){
                    queue.add(pos - 1);
                    visited[pos - 1] = true;
                }
                if(pos % mid < (mid - 1) && !is_prime[number + 1] && !visited[pos + 1]){
                    queue.add(pos + 1);
                    visited[pos + 1] = true;
                }
                if((pos - mid) > 0 && !is_prime[number - mid] && !visited[pos - mid]){
                    queue.add(pos - mid);
                    visited[pos - mid] = true;
                }
                if((pos + mid) < N && !is_prime[number + mid] && !visited[pos + mid]){
                    queue.add(pos + mid);
                    visited[pos + mid] = true;
                }
            }
            
            if(visited[N - 1]){
                return mid;
            }
        }
        
        return -1;
    }
    
    public static int smart(final BigInteger N){
        final BigInteger four = BigInteger.valueOf(4);
        final BigInteger six = BigInteger.valueOf(6);
        final BigInteger eight = BigInteger.valueOf(8);
        final BigInteger nine = BigInteger.valueOf(9);
        final BigInteger ten = BigInteger.valueOf(10);
        final BigInteger twelve = BigInteger.valueOf(12);
        final BigInteger fourteen = BigInteger.valueOf(14);
        final BigInteger fifteen = BigInteger.valueOf(15);
        final BigInteger sixteen = BigInteger.valueOf(16);
        final BigInteger twenty = BigInteger.valueOf(20);
        final BigInteger twentyone = BigInteger.valueOf(21);
        final BigInteger twentytwo = BigInteger.valueOf(22);
        final BigInteger twentyfour = BigInteger.valueOf(24);
        final BigInteger twentyfive = BigInteger.valueOf(25);
        
        if(N.equals(four)){
            return 3;
        }else if(N.equals(six)){
            return 5;
        }else if(N.equals(eight) || N.equals(nine) || N.equals(ten) || N.equals(fifteen) || N.equals(sixteen) || N.equals(twentytwo)){
            return 7;
        }else if(N.equals(twelve)){
            return 11;
        }else if(N.equals(fourteen)){
            return 13;
        }else if(N.equals(twenty) || N.equals(twentyone)){
            return 19;
        }else if(N.equals(twentyfour) || N.equals(twentyfive)){
            return 23;
        }else if(N.subtract(BigInteger.ONE).mod(eight).equals(BigInteger.ZERO) && N.subtract(eight).isProbablePrime(1000000000)){
            return 14;
        }else{
            return 8;
        }
    }
    
    // シュミレーションして法則性を掴むべき. 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        /*
        for(int i = 2; i <= 10000; i++){
            final int sim_value = simulate(i);
            if(sim_value > 0){
                final int big_value = smart(BigInteger.valueOf(i));
                if(sim_value != big_value){
                    System.out.printf("%05d : %d, %d\n", i, sim_value, big_value);
                }
            }
        }
        */
        
        BigInteger N = new BigInteger(sc.next());
        
        System.out.println(smart(N));
        
    }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX