fork download
  1. import scala.collection.immutable.SortedSet
  2. import scala.collection.immutable.SortedMap
  3.  
  4. object Main extends App {
  5. def factors(n:Int):List[Int] = {
  6. def divides(d:Int, n:Int) = (n % d) == 0
  7. def ld(n:Int):Int = ldf(2, n)
  8. def ldf(k:Int, n:Int):Int = {
  9. if (divides(k, n)) k
  10. else if ((k*k) > n) n
  11. else ldf((k+1), n)
  12. }
  13. n match {
  14. case 1 => Nil
  15. case _ => val p = ld(n); p :: factors(n / p)
  16. }
  17. }
  18.  
  19. def allSums(n:Int):Seq[(Int,Int)] = {
  20. for (i <- 2 to n/2) yield (i, n-i)
  21. }
  22.  
  23. def minMulFactorCount(s:Seq[(Int,Int)]) = {
  24. s.map{case (a,b) => factors(a*b).length}.min
  25. }
  26.  
  27.  
  28. val sumSet = SortedSet[Int]() ++ (4 to 196).filter(i => minMulFactorCount(allSums(i)) > 2)
  29. println(sumSet)
  30.  
  31. def allPairFactors(n:Int) = {
  32. def rec(i:Int):List[(Int,Int)] = {
  33. if (i*i>n) Nil
  34. else if (n%i==0) (i,n/i)::rec(i+1)
  35. else rec(i+1)
  36. }
  37. rec(2)
  38. }
  39.  
  40. val mulMap=SortedMap[Int, List[(Int,Int)]]() ++ (4 to 99*99)
  41. .map(allPairFactors(_).filter{case (a,b) => sumSet.contains(a+b)})
  42. .filter(_.length==1)
  43. .map{
  44. case el::Nil => (el._1+el._2, el._1 * el._2)
  45. case _ => (0,0)
  46. }
  47. .groupBy{case (a,b) => a}
  48.  
  49. mulMap.foreach(el => {
  50. println(el._1, el._2.map(_._2))
  51. })
  52. }
Success #stdin #stdout 0.53s 322240KB
stdin
Standard input is empty
stdout
TreeSet(11, 17, 23, 27, 29, 35, 37, 41, 47, 51, 53, 57, 59, 65, 67, 71, 77, 79, 83, 87, 89, 93, 95, 97, 101, 107, 113, 117, 119, 121, 123, 125, 127, 131, 135, 137, 143, 145, 147, 149, 155, 157, 161, 163, 167, 171, 173, 177, 179, 185, 187, 189, 191)
(11,Vector(18, 24, 28))
(17,Vector(52))
(23,Vector(76, 112))
(27,Vector(50, 92, 140, 152, 176))
(29,Vector(54, 100, 208))
(35,Vector(96, 124, 216, 304))
(37,Vector(160, 232, 336))
(41,Vector(148, 288, 400, 414, 418))
(47,Vector(172, 280, 442, 496))
(51,Vector(98, 144, 188, 308, 344, 494, 518, 578, 608, 620, 638, 644))
(53,Vector(430, 520, 592, 646, 672, 682))
(57,Vector(212, 260, 392, 470, 506, 656, 722, 782, 800, 806))
(59,Vector(220, 598, 688, 738, 814, 864))
(65,Vector(244, 406, 874, 1000, 1014))
(67,Vector(192, 472, 912, 940, 1012, 1116))
(71,Vector(268, 448, 708, 754, 880, 918, 954, 1104, 1248, 1258))
(77,Vector(292, 670, 832, 976, 1372, 1392, 1410, 1426, 1440, 1462, 1480))
(79,Vector(228, 568, 804, 960, 1180, 1488, 1504, 1548))
(83,Vector(316, 730, 852, 1072, 1216, 1342, 1566, 1666, 1692, 1720))
(87,Vector(332, 486, 632, 836, 962, 1022, 1136, 1340, 1472, 1550, 1652, 1682, 1736, 1850, 1880, 1886, 1892))
(89,Vector(498, 574, 1168, 1278, 1600, 1674, 1708, 1798, 1824, 1960, 1968, 1978))
(93,Vector(356, 902, 1040, 1106, 1406, 1460, 1562, 1856, 1922, 1952, 2030, 2072, 2120, 2150, 2156))
(95,Vector(534, 996, 1200, 1264, 1444, 1704, 1876, 1984, 2074, 2146, 2166, 2214))
(97,Vector(712, 1296, 1752, 1972, 2112, 2196, 2296, 2332))
(101,Vector(388, 658, 744, 1068, 1144, 1290, 1494, 1738, 1998, 2044, 2088, 2278, 2368, 2440, 2494, 2508, 2544))
(107,Vector(412, 606, 970, 1222, 1992, 2050, 2212, 2442, 2556, 2590, 2680, 2752, 2832))
(113,Vector(436, 642, 1030, 1212, 1552, 1786, 2070, 2136, 2490, 2542, 2686, 2920, 3136, 3172))
(117,Vector(452, 872, 1070, 1166, 1442, 1616, 1940, 2232, 2366, 2492, 2552, 2666, 2822, 2870, 2960, 3116, 3212, 3266, 3290, 3350, 3392, 3416))
(119,Vector(678, 888, 1090, 1284, 1648, 1734, 1818, 2134, 2670, 2728, 2838, 2988, 3034, 3160, 3358, 3384, 3408, 3430, 3468, 3484, 3498, 3520, 3538, 3540))
(121,Vector(904, 1308, 1498, 1854, 2020, 2178, 2328, 2668, 2848, 3108, 3280, 3504, 3604, 3648, 3660))
(123,Vector(242, 476, 590, 1130, 1526, 1712, 1976, 2060, 2222, 2376, 2522, 2660, 2726, 2912, 3026, 3320, 3362, 3440, 3476, 3572, 3692, 3710, 3740, 3752, 3776, 3782))
(125,Vector(484, 826, 1356, 1744, 1926, 2014, 2266, 2424, 2716, 2914, 3204, 3256, 3634, 3796, 3816, 3834, 3894, 3904))
(127,Vector(1276, 1582, 1776, 1962, 2140, 2392, 2472, 2626, 2910, 3382, 3652, 3760, 3792, 3976, 4012, 4020, 4032))
(131,Vector(384, 508, 1534, 1840, 2034, 2398, 2568, 2650, 2808, 2884, 3030, 3168, 3298, 3738, 3784, 3870, 3948, 3984, 4018, 4080, 4108, 4158, 4180, 4234, 4248, 4260, 4278, 4288))
(135,Vector(266, 524, 896, 1016, 1250, 1364, 1694, 1904, 2204, 2486, 2664, 2834, 2996, 3074, 3224, 3296, 3434, 3500, 3686, 3854, 3956, 4094, 4136, 4214, 4250, 4316, 4400, 4424, 4466, 4484, 4514, 4544, 4550, 4556))
(137,Vector(402, 786, 1152, 1270, 1830, 2040, 2712, 3052, 3210, 3286, 3502, 3636, 3880, 4042, 4140, 4272, 4312, 4420, 4482, 4510, 4636, 4672, 4686, 4690))
(143,Vector(556, 822, 1206, 1572, 1920, 2032, 2562, 2662, 2760, 2950, 3390, 3472, 3552, 3706, 3852, 4056, 4120, 4242, 4300, 4462, 4732, 4806, 4872, 4956, 4980, 5056, 5070, 5092, 5110, 5112))
(145,Vector(834, 1096, 1834, 2064, 2176, 2286, 3364, 3616, 3924, 4066, 4264, 4326, 4444, 4656, 4876, 4914, 4984, 5046, 5124, 5146, 5184, 5200, 5256))
(147,Vector(290, 710, 980, 1112, 1370, 1496, 2096, 2210, 2432, 2540, 3050, 3146, 3596, 3680, 3842, 3920, 4070, 4142, 4212, 4280, 4472, 4532, 4590, 4646, 4700, 4802, 4850, 4940, 4982, 5060, 5096, 5162, 5192, 5246, 5312, 5346, 5360, 5372, 5396, 5400, 5402))
(149,Vector(994, 1390, 1644, 2358, 2688, 2794, 3294, 4068, 4144, 4360, 4494, 4558, 4738, 4848, 4900, 5044, 5208, 5278, 5340, 5368, 5394, 5440, 5478, 5494, 5530, 5538, 5548))
(155,Vector(604, 894, 1314, 2224, 2466, 2584, 2814, 3144, 3250, 3456, 3556, 3844, 4114, 4366, 4600, 4746, 4816, 4884, 5014, 5136, 5194, 5304, 5356, 5454, 5500, 5626, 5664, 5734, 5766, 5796, 5824, 5874, 5896, 5934, 5950, 5964, 5976, 5994, 6004))
(157,Vector(906, 1192, 2502, 2740, 3406, 3712, 3810, 4440, 4756, 4972, 5232, 5350, 5512, 5562, 5656, 5742, 5820, 5856, 5890, 5952, 6052, 6072, 6132, 6142, 6156, 6162))
(161,Vector(474, 628, 1510, 1788, 2190, 2320, 2448, 2698, 3058, 3174, 3288, 3930, 4128, 4224, 4318, 4758, 5290, 5424, 5488, 5668, 5724, 5778, 5974, 6018, 6060, 6100, 6138, 6208, 6240, 6298, 6324, 6348, 6408, 6424, 6438, 6474, 6478))
(163,Vector(942, 1812, 2086, 3336, 3562, 4192, 4480, 4572, 5160, 5452, 5650, 5886, 5992, 6136, 6180, 6262, 6336, 6402, 6432, 6532, 6586, 6600, 6622, 6636, 6640))
(167,Vector(652, 1570, 2416, 2682, 3066, 3892, 4110, 4216, 4422, 4716, 4810, 4992, 5080, 5332, 5490, 5566, 5640, 6102, 6216, 6322, 6372, 6420, 6466, 6592, 6666, 6700, 6732, 6790, 6816, 6862, 6900, 6942, 6952, 6960, 6966, 6970, 6972))
(171,Vector(338, 668, 1148, 1304, 1458, 2054, 2198, 2480, 2618, 2888, 3020, 3278, 3404, 3888, 4118, 4340, 4448, 4658, 4760, 4860, 4958, 5054, 5240, 5504, 5588, 5750, 5828, 5978, 6050, 6188, 6254, 6318, 6440, 6498, 6554, 6608, 6660, 6758, 6804, 6848, 6890, 6968, 7004, 7070, 7100, 7128, 7154, 7178, 7200, 7220, 7238, 7268, 7298, 7304, 7310))
(173,Vector(1002, 1630, 2370, 2512, 3322, 3576, 4060, 4402, 4726, 4932, 5032, 5502, 5590, 5676, 5760, 5842, 6076, 6360, 6490, 6726, 6780, 6832, 6976, 7062, 7176, 7210, 7242, 7272, 7300, 7350, 7372, 7392, 7426, 7440, 7462, 7470, 7476))
(177,Vector(692, 860, 1670, 1826, 2282, 3140, 3926, 4172, 4292, 4862, 4970, 5180, 5282, 5480, 5576, 5762, 5852, 6026, 6110, 6272, 6350, 6500, 6572, 6776, 6902, 6962, 7076, 7130, 7232, 7412, 7490, 7526, 7592, 7622, 7650, 7676, 7700, 7722, 7742, 7760, 7776, 7790, 7802, 7820, 7826, 7830, 7832))
(179,Vector(1038, 2004, 2158, 2608, 3454, 3720, 3978, 4104, 4228, 4470, 4818, 5560, 5658, 5754, 5848, 6118, 6288, 6528, 6604, 6678, 6820, 6888, 6954, 7018, 7080, 7198, 7360, 7458, 7504, 7548, 7590, 7630, 7668, 7704, 7738, 7770, 7828, 7878, 7900, 7920, 7954, 7968, 7980, 7990, 8008, 8010))
(185,Vector(724, 1074, 1246, 2076, 2704, 3006, 3586, 4266, 4396, 4774, 5134, 5364, 5476, 5694, 5800, 6394, 6576, 6664, 6834, 6996, 7074, 7150, 7224, 7296, 7366, 7434, 7500, 7564, 7626, 7744, 7906, 7956, 8050, 8094, 8136, 8176, 8214, 8284, 8316, 8346, 8374, 8446, 8466, 8484, 8500, 8514, 8526, 8536, 8544, 8554, 8556))
(187,Vector(732, 1086, 1432, 2422, 3340, 3772, 3912, 4710, 5202, 5436, 5662, 6580, 6672, 6850, 6936, 7260, 7336, 7552, 7620, 7750, 7872, 7986, 8040, 8092, 8142, 8236, 8322, 8362, 8436, 8502, 8532, 8560, 8586, 8610, 8632, 8652, 8670, 8686, 8712, 8722, 8730, 8736, 8742))
(189,Vector(374, 1274, 1448, 1790, 1958, 2288, 2768, 2924, 3674, 3818, 4100, 4238, 4508, 4898, 5024, 5624, 5738, 5960, 6068, 6278, 6578, 6674, 6860, 6950, 7124, 7208, 7448, 7524, 7598, 7670, 7740, 7808, 7874, 8000, 8060, 8118, 8174, 8228, 8330, 8378, 8468, 8510, 8588, 8624, 8690, 8720, 8748, 8774, 8798, 8820, 8840, 8858, 8874, 8888, 8900, 8918, 8924, 8928, 8930))
(191,Vector(1464, 1810, 2148, 2314, 3114, 3718, 4008, 4150, 4564, 4698, 5338, 5580, 5698, 5814, 6040, 6258, 6364, 6864, 6958, 7050, 7228, 7314, 7398, 7638, 7714, 7788, 7860, 8064, 8128, 8308, 8364, 8418, 8520, 8568, 8614, 8778, 8814, 8848, 8880, 8938, 8964, 8988, 9010, 9030, 9048, 9064, 9078, 9090, 9100, 9108, 9114, 9118, 9120))