結果

問題 No.458 異なる素数の和
コンテスト
ユーザー compass19
提出日時 2016-12-09 02:40:34
言語 Java
(openjdk 23)
結果
TLE  
実行時間 -
コード長 1,728 bytes
コンパイル時間 1,920 ms
コンパイル使用メモリ 77,136 KB
実行使用メモリ 108,872 KB
最終ジャッジ日時 2024-11-28 16:08:37
合計ジャッジ時間 32,069 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 18 WA * 1 RE * 1 TLE * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.Scanner;
class Sample{


	public static boolean is_prime(int n, int []primes, int num_primes){
		for (int i = 0; i < num_primes; i++) {
			int prime = primes[i];
			if (n%prime == 0){
				return false;
			}
		}
		return true;
	}

	public static boolean is_in_keys(int x, int []keys, int num_keys){
		for (int i = 0; i < num_keys; i++) {
			if (x == keys[i]){
				return true;
			}
		}
		return false;
	}


	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int num_primes = 1;
		int primes[] = new int[n];
		int sum_primes[] = new int[n];
		int _sum = 2;

		primes[0] = 2;
		sum_primes[0] = 2;

		for (int i = 3; i < n+1; i++) {
			if (is_prime(i, primes, num_primes)){
				_sum += i;
				primes[num_primes] = i;
				sum_primes[num_primes] = _sum;
				num_primes += 1;
			}
		}

		int data[] = new int[n+1];
		for (int i = 0; i < n+1; i++) {
			data[i] = -1;
		}
		int keys[] = new int[n+1];
		int num_keys = 0;
		for (int i = num_primes-1; i > -1; i--) {
			int prime = primes[i];
			//System.out.println("prime" + prime);
			//System.out.println(data[8]);
			_sum = sum_primes[i];
			if (!is_in_keys(prime, keys, num_keys)){
				data[prime] = 1;
				keys[num_keys] = prime;
				num_keys += 1;
			}
			for (int j = 0; j < num_keys-1; j++) {
				int key = keys[j];
				if (!(key+prime > n) && (!(key+_sum < n))){
					//.out.println(key+prime);
					if (!is_in_keys(key+prime, keys, num_keys)){
						data[key+prime] = data[key] + 1;
						keys[num_keys] = key+prime;
						num_keys += 1;
					}
					else{
						if (data[key+prime] < data[key] + 1){
							data[key+prime] = data[key] + 1;
						}
					}
				}
			}
		}
		System.out.println(data[n]);
	}
}
0