fork download
copy 
  1. package ramenj;
  2.  
  3. import java.math.BigInteger;
  4. import java.util.Optional;
  5. import java.util.OptionalLong;
  6. import java.util.function.Function;
  7. import java.util.function.Predicate;
  8. import java.util.stream.LongStream;
  9.  
  10. /**
  11.  * RamenJ (ラーメン素数)制限時間内に算出した最大の素数をラーメンと呼称する (制限時間)ラーメンの計算は3分以内(180秒以内)とし超えてはならない
  12.  * (All or Nothingの原則)制限時間内に計算が完了しなかった場合、ラーメンは2とする
  13.  * (既知の素数)計算なしに使用してよい既知の素数は2と3とする、それ以外の素数は未知とする
  14.  * 
  15.  * @author noramen
  16.  */
  17. public class Program {
  18. 	public final static int ramen2 = 2;
  19. 	public final static int ramen3 = 3;
  20. 	public final static int noramen = ramen2;
  21.  
  22. 	public static void main(String args[]) {
  23. 		long start = System.currentTimeMillis();
  24.  
  25. 		// int ramen = Ramen1(); // NG
  26. 		// long ramen = Ramen2(); // OK 9223372036854775783
  27. 		// long ramen = Ramen3(); // OK 9223372036854775783
  28. 		// long ramen = Ramen3_1(); // OK 9223372036854775783
  29. 		// long ramen = Ramen3_2(); // OK 9223372036854775783
  30.  
  31. 		// BigInteger ramen = Ramen4(); // OK 18446744073709551629
  32. 		// BigInteger ramen = Ramen5(); // OK 18446744073709551629
  33.  
  34. 		// BigInteger ramen = Ramen6(2l, 1l, 1l, 1l); // Ramen5()と同値
  35. 		// BigInteger ramen = Ramen6(5l, 1l, 2l, 1l); // OK 46116860184273879079
  36. 		// BigInteger ramen = Ramen6(6l, 1l, 5l, 2l); // OK 55340232221128654843
  37. 		// BigInteger ramen = Ramen6(13l, 2l, 5l, 2l); // OK 59951918239556042783
  38. 		// BigInteger ramen = Ramen6(68l, 10l, 5l, 2l); // OK 62718929850612475567
  39.  
  40. 		// BigInteger ramen = Ramen7(69l, 10l, 5l, 2l); // OK 63641267054297953129
  41. 		// BigInteger ramen = Ramen7(9l, 1l, 3l, 1l); // OK 83010348331692982271
  42. 		// BigInteger ramen = Ramen7(11l, 1l, 3l, 1l); // OK 101457092405402533879
  43. 		// BigInteger ramen = Ramen7(112l, 10l, 3l, 1l); //OK 103301766812773489067
  44. 		// BigInteger ramen = Ramen7(114l, 10l, 346l, 100l); // OK 105146441220144444251
  45. 		// BigInteger ramen = Ramen7(116l, 10l, 346l, 100l); // NG
  46. 		// BigInteger ramen = Ramen7(118l, 10l, 346l, 100l); // NG
  47. 		// BigInteger ramen = Ramen7(12l, 1l, 346l, 100l); // NG
  48.  
  49. 		// BigInteger ramen = Ramen8(114l, 10l, 346l, 100l); // OK 105146441220144444251
  50. 		// BigInteger ramen = Ramen8(12l, 1l, 346l, 100l); // OK 110680464442257309779
  51. 		// BigInteger ramen = Ramen8(13l, 1l, 346l, 100l); // OK 119903836479112085531
  52. 		// BigInteger ramen = Ramen8(14l, 1l, 346l, 100l); // OK 129127208515966861349
  53. 		// BigInteger ramen = Ramen8(16l, 1l, 4l, 1l); // OK 147573952589676412931
  54. 		// BigInteger ramen = Ramen8(18l, 1l, 4l, 1l); // OK 166020696663385964539
  55. 		//BigInteger ramen = Ramen8(19l, 1l, 4l, 1l); // OK 175244068700240740367
  56. 		BigInteger ramen = Ramen8(20l, 1l, 4l, 1l); // OK? 184467440737095516163
  57.  
  58. 		System.out.println();
  59. 		System.out.println(ramen);
  60.  
  61. 		long end = System.currentTimeMillis();
  62. 		System.out.println((end - start) / 1000);
  63. 	}
  64.  
  65. 	/**
  66. 	 * i,j,kを使った逐次法 (NG)5分経っても終らない
  67. 	 * 
  68. 	 * @return noramen
  69. 	 */
  70. 	static int Ramen1() {
  71. 		int ramen = 2;
  72.  
  73. 		for (int i = 3; i <= Integer.MAX_VALUE; i += 2) {
  74. 			boolean k = true;
  75. 			for (int j = 3; j <= Math.sqrt(i); j += 2) {
  76. 				if (i % j == 0) {
  77. 					k = false;
  78. 					break;
  79. 				}
  80. 			}
  81.  
  82. 			if (k) {
  83. 				ramen = i;
  84. 				System.out.println(i);
  85. 			}
  86. 		}
  87.  
  88. 		return ramen;
  89. 	}
  90.  
  91. 	/**
  92. 	 * Long.MAX_VALUEから逆順でAll or Nothing (OK)約14秒で出る
  93. 	 * 
  94. 	 * @return 9223372036854775783
  95. 	 */
  96. 	static long Ramen2() {
  97. 		for (long i = Long.MAX_VALUE; i >= 3; i -= 2) {
  98. 			boolean flag = true;
  99. 			for (long j = 3; j <= Math.sqrt(i); j += 2) {
  100. 				if (i % j == 0) {
  101. 					flag = false;
  102. 					break;
  103. 				}
  104. 			}
  105.  
  106. 			if (flag) {
  107. 				return i;
  108. 			}
  109. 		}
  110. 		return noramen;
  111. 	}
  112.  
  113. 	/**
  114. 	 * Ramen2()のうちflagをFunctionで書き直したもの (OK)約14秒で出る
  115. 	 * 
  116. 	 * @return 9223372036854775783
  117. 	 */
  118. 	static long Ramen3() {
  119. 		Function<Long, Boolean> isramen = t -> {
  120. 			for (long i = 3; i <= Math.sqrt(t); i += 2) {
  121. 				if (t % i == 0) {
  122. 					return false;
  123. 				}
  124. 			}
  125. 			return true;
  126. 		};
  127.  
  128. 		for (long i = Long.MAX_VALUE; i >= 3; i -= 2) {
  129. 			if (isramen.apply(i)) {
  130. 				return i;
  131. 			}
  132. 		}
  133.  
  134. 		return noramen;
  135. 	}
  136.  
  137. 	/**
  138. 	 * Ramen3()の素数判定(試し割り法)を+=2ではなく++になるよう書き直したもの (OK)約12秒かかる
  139. 	 * 
  140. 	 * @return 9223372036854775783
  141. 	 */
  142. 	static long Ramen3_1() {
  143. 		Function<Long, Boolean> isramen = t -> {
  144. 			long halfSqrt = (long) (Math.sqrt(t) / 2);
  145. 			for (long i = 1; i <= halfSqrt; i++) {
  146. 				if (t % (i * 2 + 1) == 0) {
  147. 					return false;
  148. 				}
  149. 			}
  150. 			return true;
  151. 		};
  152.  
  153. 		for (long i = Long.MAX_VALUE; i >= 3; i -= 2) {
  154. 			if (isramen.apply(i)) {
  155. 				return i;
  156. 			}
  157. 		}
  158.  
  159. 		return noramen;
  160. 	}
  161.  
  162. 	/**
  163. 	 * Ramen3_1()をLongStreamで書き直しparallelしたもの (OK)約7～9秒かかる
  164. 	 * 
  165. 	 * @return 9223372036854775783
  166. 	 */
  167. 	static long Ramen3_2() {
  168. 		Function<Long, Boolean> isramen = t -> {
  169. 			long halfSqrt = (long) (Math.sqrt(t) / 2);
  170. 			OptionalLong findAny = LongStream.rangeClosed(1, halfSqrt).parallel().filter(x -> t % (x * 2 + 1) == 0)
  171. 					.findAny();
  172. 			return !findAny.isPresent();
  173. 		};
  174.  
  175. 		for (long i = Long.MAX_VALUE; i >= 3; i -= 2) {
  176. 			if (isramen.apply(i)) {
  177. 				return i;
  178. 			}
  179. 		}
  180.  
  181. 		return noramen;
  182. 	}
  183.  
  184. 	/**
  185. 	 * Ramen3()をBigIntegerに書き直したもの。また (1)sqrtを使わずpowを使用
  186. 	 * (2)ループ処理でをstart3,step2→start5,step6に書き換え
  187. 	 * (3)BigInteger.nextProbablePrimeを使用(OK)約128～140秒かかる
  188. 	 * 
  189. 	 * @return 18446744073709551629
  190. 	 */
  191. 	static BigInteger Ramen4() {
  192. 		Function<BigInteger, Boolean> isramen = t -> {
  193. 			BigInteger i = BigInteger.valueOf(5l);
  194. 			while (i.pow(2).compareTo(t) <= 0) {
  195. 				if (t.remainder(i) == BigInteger.ZERO
  196. 						|| t.remainder(i.add(BigInteger.valueOf(2l))) == BigInteger.ZERO) {
  197. 					return false;
  198. 				}
  199. 				i = i.add(BigInteger.valueOf(6l));
  200. 			}
  201. 			return true;
  202. 		};
  203.  
  204. 		BigInteger ramen = BigInteger.valueOf(Long.MAX_VALUE).multiply(BigInteger.valueOf(2l));
  205. 		if (ramen.remainder(BigInteger.valueOf(2l)) == BigInteger.ZERO) {
  206. 			ramen = ramen.add(BigInteger.ONE);
  207. 		}
  208. 		while (!isramen.apply(ramen)) {
  209. 			System.out.println(ramen + " is not ramen");
  210. 			ramen = ramen.nextProbablePrime();
  211. 		}
  212. 		return ramen;
  213. 	}
  214.  
  215. 	/**
  216. 	 * Ramen4()をStreamで書き直しparallelしたもの ループ処理でをstart3,step2に戻し√x/2に近似で求める
  217. 	 * (OK)約80秒かかる
  218. 	 * 
  219. 	 * @return 18446744073709551629
  220. 	 */
  221. 	static BigInteger Ramen5() {
  222. 		Function<BigInteger, Long> halfsqrt = x -> {
  223. 			BigInteger xnn = BigInteger.valueOf((long) Math.sqrt(Long.MAX_VALUE));
  224. 			BigInteger xn = BigInteger.ZERO;
  225. 			while (xnn.subtract(xn).abs().compareTo(BigInteger.ONE) > 0) {
  226. 				xn = xnn;
  227. 				xnn = x.divide(xnn).add(xnn).divide(BigInteger.valueOf(2l));
  228. 			}
  229. 			return xnn.divide(BigInteger.valueOf(2l)).longValueExact();
  230. 		};
  231.  
  232. 		Function<BigInteger, Boolean> isramen = t -> {
  233. 			LongStream stream = LongStream.rangeClosed(1, halfsqrt.apply(t));
  234. 			Optional<BigInteger> findAny = stream.parallel()
  235. 					.mapToObj(i -> BigInteger.valueOf(i).multiply(BigInteger.valueOf(2l).add(BigInteger.ONE)))
  236. 					.filter(i -> t.remainder(i) == BigInteger.ZERO).findAny();
  237. 			return !findAny.isPresent();
  238. 		};
  239.  
  240. 		BigInteger ramen = BigInteger.valueOf(Long.MAX_VALUE).multiply(BigInteger.valueOf(2l));
  241. 		ramen = ramen.nextProbablePrime();
  242. 		while (!isramen.apply(ramen)) {
  243. 			System.out.println(ramen + " is not ramen");
  244. 			ramen = ramen.nextProbablePrime();
  245. 		}
  246. 		return ramen;
  247. 	}
  248.  
  249. 	/**
  250. 	 * Ramen5()にパラメーターを付与し変更しやすいよう変形したもの
  251. 	 * 
  252. 	 * @param mul1
  253. 	 *            開始数の乗数
  254. 	 * @param div1
  255. 	 *            開始数の除数
  256. 	 * @param mul2
  257. 	 *            ニュートン近似の乗数
  258. 	 * @param div2
  259. 	 *            ニュートン近似の除数
  260. 	 * @return Ramen6(13l, 2l, 5l, 2l)=59951918239556042783
  261. 	 */
  262. 	static BigInteger Ramen6(long mul1, long div1, long mul2, long div2) {
  263. 		Function<BigInteger, Long> halfsqrt = x -> {
  264. 			BigInteger xnn = BigInteger.valueOf((long) Math.sqrt(Long.MAX_VALUE)).multiply(BigInteger.valueOf(mul2))
  265. 					.divide(BigInteger.valueOf(div2));
  266. 			BigInteger xn = BigInteger.ZERO;
  267. 			while (xnn.subtract(xn).abs().compareTo(BigInteger.ONE) > 0) {
  268. 				xn = xnn;
  269. 				xnn = x.divide(xnn).add(xnn).divide(BigInteger.valueOf(2l));
  270. 			}
  271. 			return xnn.divide(BigInteger.valueOf(2l)).longValueExact();
  272. 		};
  273.  
  274. 		Function<BigInteger, Boolean> isramen = t -> {
  275. 			LongStream stream = LongStream.rangeClosed(1, halfsqrt.apply(t));
  276. 			Optional<BigInteger> findAny = stream.parallel()
  277. 					.mapToObj(i -> BigInteger.valueOf(i).multiply(BigInteger.valueOf(2l).add(BigInteger.ONE)))
  278. 					.filter(i -> t.remainder(i) == BigInteger.ZERO).findAny();
  279. 			return !findAny.isPresent();
  280. 		};
  281.  
  282. 		BigInteger ramen = BigInteger.valueOf(Long.MAX_VALUE).multiply(BigInteger.valueOf(mul1))
  283. 				.divide(BigInteger.valueOf(div1));
  284. 		ramen = ramen.nextProbablePrime();
  285. 		while (!isramen.apply(ramen)) {
  286. 			System.out.println(ramen + " is not ramen");
  287. 			ramen = ramen.nextProbablePrime();
  288. 		}
  289. 		return ramen;
  290. 	}
  291.  
  292. 	/**
  293. 	 * Ramen6の (1)mapToObj内をBigIntegerからLong (2)findAny.isPresentからnoneMatch
  294. 	 * (3)remainder判定を==からcompareTo==
  295. 	 * (4)isramenをFunction<BigInteger,Boolean>からPredicate<BigInteger> 、で書き直したもの
  296. 	 * 
  297. 	 * @param mul1
  298. 	 *            開始数の乗数
  299. 	 * @param div1
  300. 	 *            開始数の除数
  301. 	 * @param mul2
  302. 	 *            ニュートン近似の乗数
  303. 	 * @param div2
  304. 	 *            ニュートン近似の除数
  305. 	 * @return Ramen7(114l, 10l, 346l, 100l)=105146441220144444251
  306. 	 */
  307. 	static BigInteger Ramen7(long mul1, long div1, long mul2, long div2) {
  308. 		Function<BigInteger, Long> halfsqrt = x -> {
  309. 			BigInteger xnn = BigInteger.valueOf((long) Math.sqrt(Long.MAX_VALUE)).multiply(BigInteger.valueOf(mul2))
  310. 					.divide(BigInteger.valueOf(div2));
  311. 			BigInteger xn = BigInteger.ZERO;
  312. 			while (xnn.subtract(xn).abs().compareTo(BigInteger.ONE) > 0) {
  313. 				xn = xnn;
  314. 				xnn = x.divide(xnn).add(xnn).divide(BigInteger.valueOf(2l));
  315. 			}
  316. 			return xnn.divide(BigInteger.valueOf(2l)).longValueExact();
  317. 		};
  318.  
  319. 		Predicate<BigInteger> isramen = t -> LongStream.rangeClosed(1, halfsqrt.apply(t)).parallel()
  320. 				.mapToObj(i -> BigInteger.valueOf(i * 2l + 1l))
  321. 				.noneMatch(i -> t.remainder(i).compareTo(BigInteger.ZERO) == 0);
  322.  
  323. 		BigInteger ramen = BigInteger.valueOf(Long.MAX_VALUE).multiply(BigInteger.valueOf(mul1))
  324. 				.divide(BigInteger.valueOf(div1));
  325. 		ramen = ramen.nextProbablePrime();
  326. 		while (!isramen.test(ramen)) {
  327. 			System.out.println(ramen + " is not ramen");
  328. 			ramen = ramen.nextProbablePrime();
  329. 		}
  330. 		return ramen;
  331. 	}
  332.  
  333. 	/**
  334. 	 * Ramen7のhalfsqrtからsextantsqrtに書き換えたもの
  335. 	 * 
  336. 	 * @param mul1
  337. 	 *            開始数の乗数
  338. 	 * @param div1
  339. 	 *            開始数の除数
  340. 	 * @param mul2
  341. 	 *            ニュートン近似の乗数
  342. 	 * @param div2
  343. 	 *            ニュートン近似の除数
  344. 	 * @return
  345. 	 */
  346. 	static BigInteger Ramen8(long mul1, long div1, long mul2, long div2) {
  347. 		Function<BigInteger, Long> sextantsqrt = x -> {
  348. 			BigInteger xnn = BigInteger.valueOf((long) Math.sqrt(Long.MAX_VALUE)).multiply(BigInteger.valueOf(mul2))
  349. 					.divide(BigInteger.valueOf(div2));
  350. 			BigInteger xn = BigInteger.ZERO;
  351.  
  352. 			do {
  353. 				xn = xnn;
  354. 				xnn = x.divide(xnn).add(xnn).divide(BigInteger.valueOf(2l));
  355. 			} while (xnn.subtract(xn).abs().compareTo(BigInteger.ONE) > 0);
  356.  
  357. 			return xnn.max(xn).divide(BigInteger.valueOf(6l)).longValueExact();
  358. 		};
  359.  
  360. 		Function<BigInteger, Boolean> isramen = t -> {
  361. 			if (t.remainder(BigInteger.valueOf(2l)).compareTo(BigInteger.ZERO) == 0
  362. 					|| t.remainder(BigInteger.valueOf(3l)).compareTo(BigInteger.ZERO) == 0) {
  363. 				return false;
  364. 			}
  365.  
  366. 			return LongStream.range(0, sextantsqrt.apply(t)).parallel().mapToObj(i -> BigInteger.valueOf(i * 6l + 5l))
  367. 					.noneMatch(i -> t.remainder(i).compareTo(BigInteger.ZERO) == 0
  368. 							|| t.remainder(i.add(BigInteger.valueOf(2l))).compareTo(BigInteger.ZERO) == 0);
  369. 		};
  370.  
  371. 		BigInteger ramen = BigInteger.valueOf(Long.MAX_VALUE).multiply(BigInteger.valueOf(mul1))
  372. 				.divide(BigInteger.valueOf(div1));
  373. 		ramen = ramen.nextProbablePrime();
  374. 		while (!isramen.apply(ramen)) {
  375. 			System.out.println(ramen + " is not ramen");
  376. 			ramen = ramen.nextProbablePrime();
  377. 		}
  378. 		return ramen;
  379. 	}
  380. }
  381.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:17: error: class Program is public, should be declared in a file named Program.java
public class Program {
       ^
1 error
stdout
copy 
Standard output is empty
https://ideone.com/pemh9M
language:
Java (HotSpot 12)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!