結果

問題 No.371 ぼく悪いプライムじゃないよ
コンテスト
ユーザー ぴろず
提出日時 2016-07-18 23:12:26
言語 Java
(openjdk 23)
結果
WA  
実行時間 -
コード長 2,473 bytes
コンパイル時間 2,612 ms
コンパイル使用メモリ 79,312 KB
実行使用メモリ 61,524 KB
最終ジャッジ日時 2024-10-15 17:08:02
合計ジャッジ時間 10,014 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 2
other AC * 12 WA * 8 TLE * 1 -- * 21
権限があれば一括ダウンロードができます

ソースコード

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