結果

問題 No.371 ぼく悪いプライムじゃないよ
ユーザー ぴろずぴろず
提出日時 2016-07-18 23:12:26
言語 Java21
(openjdk 21)
結果
WA  
実行時間 -
コード長 2,473 bytes
コンパイル時間 2,262 ms
コンパイル使用メモリ 79,028 KB
実行使用メモリ 59,528 KB
最終ジャッジ日時 2024-04-23 16:37:47
合計ジャッジ時間 8,125 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 131 ms
59,528 KB
testcase_01 AC 134 ms
53,952 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 AC 127 ms
41,808 KB
testcase_05 AC 128 ms
41,580 KB
testcase_06 AC 127 ms
41,760 KB
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 AC 131 ms
41,880 KB
testcase_11 AC 137 ms
41,956 KB
testcase_12 WA -
testcase_13 AC 129 ms
41,908 KB
testcase_14 WA -
testcase_15 AC 132 ms
41,524 KB
testcase_16 WA -
testcase_17 WA -
testcase_18 AC 128 ms
41,688 KB
testcase_19 WA -
testcase_20 AC 130 ms
41,532 KB
testcase_21 AC 147 ms
41,692 KB
testcase_22 AC 129 ms
41,924 KB
testcase_23 AC 153 ms
41,828 KB
testcase_24 TLE -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
testcase_42 -- -
testcase_43 -- -
testcase_44 -- -
testcase_45 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

package no371;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static ArrayList<Integer> primeList = primeList(110000);
	
	//嘘っぽい
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long l = sc.nextLong();
		long h = sc.nextLong();
		System.out.println(better(l,h));
//		long r = 10000000000L;
//		while(true) {
//			long stime = System.nanoTime();
//			long ans = better(3,r);
//			System.out.println(r + "->" + ans);
//			System.out.println((System.nanoTime() - stime) / 1000000 + " ms");
//			System.out.println("factorize:" + primeFactorL(primeList, ans));
//			r = ans - 1;
//		}
		
	}
	
	public static long better(long l,long h) {
		if (h - l <= 100) {
			return naive(l, h);
		}
		long x = -1;
		for(long p: primeList) {
			long sq = p * p;
			if (sq > h) {
				break;
			}
			if (l <= sq) {
				x = p;
			}
		}
		if (x < 0) {
			return naive(l,h);
		}
		long ans = x * x;
		for(long p: primeList) {
			long y = x * p;
			if (y <= h && y >= ans) {
				ans = y;
			}
		}
		return ans;
	}
	
	public static long naive(long l,long h) {
		int best = -1;
		long ans = Long.MAX_VALUE;
		for(long n=h;n>=l;n--) {
			if (best >= 0) {
				long p = primeList.get(best + 1);
//				System.out.println(n - p * p);
				if (p * p > n) {
					break;
				}
			}
			int ind = -1;
			for(int i=0;i<primeList.size();i++) {
				if (n % primeList.get(i) == 0) {
					ind = i;
					break;
				}
			}
			if (ind == -1) {
				continue; //prime
			}
			if (ind > best) {
				best = ind;
				ans = n;
			}
		}
		return ans;
	}

	public static boolean[] isPrimeArray(int max) {
		boolean[] isPrime = new boolean[max+1];
		Arrays.fill(isPrime, true);
		isPrime[0] = isPrime[1] = false;
		for(int i=2;i*i<=max;i++) {
			if (isPrime[i]) {
				int j = i * 2;
				while(j<=max) {
					isPrime[j] = false;
					j += i;
				}
			}
		}
		return isPrime;
	}
	public static ArrayList<Integer> primeList(int max) {
		boolean[] isPrime = isPrimeArray(max);
		ArrayList<Integer> primeList = new ArrayList<Integer>();
		for(int i=2;i<=max;i++) {
			if (isPrime[i]) {
				primeList.add(i);
			}
		}
		return primeList;
	}
	
	public static ArrayList<Long> primeFactorL(ArrayList<Integer> primeList,long num) {
		ArrayList<Long> ret = new ArrayList<Long>();
		for(int p:primeList) {
			while(num % p == 0) {
				num /= p;
				ret.add((long) p);
			}
		}
		if (num > 1) {
			ret.add(num);
		}
		return ret;
	}
}
0