Problem Statement
A number is composite if it is a positive integer with at least three divisors. The smallest few composite numbers are 4, 6, 8, 9, 10, 12, ...
A number is called prefix-composite if all its non-empty prefixes are composite. For example, the number 87343 is prefix-composite becase each of the numbers 8, 87, 873, 8734, and 87343 is composite.
Given two integers A and B, find the smallest and the greatest prefix-composite number in the closed interval [A, B].
Return a
Definition
- Class:
- PrefixComposite
- Method:
- minMax
- Parameters:
- long, long
- Returns:
- long[]
- Method signature:
- long[] minMax(long A, long B)
- (be sure your method is public)
Constraints
- A and B will be between 1 and 10^11, inclusive.
- A will be smaller than or equal to B.
Examples
1
3
Returns: { }
The number 1 is neither composite nor prime, and the numbers 2 and 3 are prime.
1
4
Returns: {4, 4 }
If there is exactly one prefix-composite number in the given interval, the return value should contain it twice - it is both the smallest and the greatest one in that range.
123
838
Returns: {400, 828 }
409
87343
Returns: {420, 87343 }
979797
979898
Returns: { }
600
703
Returns: {600, 699 }
1
100000000000
Returns: {4, 99999999999 }
37337999
37337999
Returns: { }
Fun fact: the number 37,337,999 is prefix-prime - each of its prefixes is prime.
22
39
Returns: { }
1
300000
Returns: {4, 99999 }
409
10000
Returns: {420, 9999 }
1
1
Returns: { }
1
2
Returns: { }
1
3
Returns: { }
1
4
Returns: {4, 4 }
1
5
Returns: {4, 4 }
1
6
Returns: {4, 6 }
1
7
Returns: {4, 6 }
2
2
Returns: { }
2
3
Returns: { }
2
4
Returns: {4, 4 }
2
5
Returns: {4, 4 }
2
6
Returns: {4, 6 }
2
7
Returns: {4, 6 }
3
3
Returns: { }
3
4
Returns: {4, 4 }
3
5
Returns: {4, 4 }
3
6
Returns: {4, 6 }
3
7
Returns: {4, 6 }
4
4
Returns: {4, 4 }
4
5
Returns: {4, 4 }
4
6
Returns: {4, 6 }
4
7
Returns: {4, 6 }
5
5
Returns: { }
5
6
Returns: {6, 6 }
5
7
Returns: {6, 6 }
6
6
Returns: {6, 6 }
6
7
Returns: {6, 6 }
522
575
Returns: { }
426
445
Returns: {426, 445 }
81
772
Returns: {81, 699 }
447
629
Returns: {447, 629 }
202
497
Returns: {400, 497 }
325
775
Returns: {400, 699 }
784
982
Returns: {800, 982 }
156
417
Returns: {400, 408 }
902
932
Returns: {902, 932 }
537
728
Returns: {600, 699 }
739
857
Returns: {800, 856 }
211
918
Returns: {400, 918 }
506
679
Returns: {600, 669 }
340
568
Returns: {400, 498 }
16
868
Returns: {40, 868 }
263
940
Returns: {400, 940 }
449
593
Returns: {450, 498 }
310
991
Returns: {400, 990 }
68
355
Returns: {68, 99 }
431
580
Returns: {440, 498 }
291757
449218
Returns: {400000, 448998 }
374934
594328
Returns: {400000, 498999 }
163676
829355
Returns: {400000, 828999 }
899080
996221
Returns: {900000, 996221 }
195922
531545
Returns: {400000, 498999 }
34067
748511
Returns: {40000, 699999 }
338674
575467
Returns: {400000, 498999 }
206504
284691
Returns: { }
262034
999835
Returns: {400000, 999835 }
344965
959980
Returns: {400000, 959980 }
45895
381221
Returns: {45895, 99999 }
32501
948152
Returns: {40000, 948152 }
147731
708325
Returns: {400000, 699999 }
229302
248153
Returns: { }
119022
309896
Returns: { }
208399
797489
Returns: {400000, 699999 }
766466
870607
Returns: {800000, 870607 }
374432
831502
Returns: {400000, 828999 }
53968
628333
Returns: {60000, 628333 }
187475
233792
Returns: { }
69898989989
99889989889
Returns: {69898989990, 99889989888 }
89999386
44094576456
Returns: {90000000, 44088999999 }
8073141342
89537058698
Returns: {8073141342, 88999999999 }
4899
95584688
Returns: {4899, 95584688 }
481088621
81304265332
Returns: {481088621, 81304265332 }
6204966
89989888898
Returns: {6204966, 88999999999 }
50295891969
87333673274
Returns: {60000000000, 87333673274 }
4804331881
67091883220
Returns: {4804331881, 66999999999 }
9898898899
44663851401
Returns: {9898898900, 44663851401 }
690480829
87055441227
Returns: {690480829, 87055441227 }
92054521
8899888889
Returns: {92054521, 8899888889 }
82063
20359911957
Returns: {82063, 9999999999 }
69899320107
76269122601
Returns: {69900000000, 69999999999 }
692688
69057067264
Returns: {692688, 69057067264 }
299999
85636973764
Returns: {400000, 85629999999 }
99
98898999989
Returns: {99, 98898999988 }
618
26770179343
Returns: {620, 9999999999 }
8989889899
69898989899
Returns: {9000000000, 69898989898 }
15602287469
87101430412
Returns: {40000000000, 87101430412 }
99996
44154453498
Returns: {99996, 44154453498 }
699
920639055
Returns: {699, 920639055 }
4643537428
9901347593
Returns: {4644000000, 9900999999 }
33679854882
73897273517
Returns: {40000000000, 69999999999 }
299999599
25013801515
Returns: {400000000, 9999999999 }
9690652291
89898889998
Returns: {9690652291, 88999999999 }
69
8769423311
Returns: {69, 8769423311 }
34850385413
69888898889
Returns: {40000000000, 69888898889 }
6966343424
6989898889
Returns: {6966343424, 6989898888 }
422586662
66735514571
Returns: {422586662, 66729999999 }
34782327307
89989989989
Returns: {40000000000, 88999999999 }
441550
8898998898
Returns: {441550, 8898998898 }
89098
91922390943
Returns: {90000, 91899999999 }
42999999
69889999988
Returns: {42999999, 69889899999 }
4925799254
90997981495
Returns: {4925799254, 90996999999 }
6889988999
68988989899
Returns: {6890000000, 68988989898 }
89888998899
89989999889
Returns: { }
28083003299
85483571449
Returns: {40000000000, 85483571449 }
25782121
9099958976
Returns: {40000000, 9099958976 }
88988988899
96248500528
Returns: {88988988900, 96248500528 }
8769874045
83774034433
Returns: {8769874045, 82899999999 }
34810971653
51741452977
Returns: {40000000000, 49899999999 }
89888989889
99988989899
Returns: {90000000000, 99988989889 }
69898888917
97926138238
Returns: {69898889000, 96999999999 }
69954997999
99889888998
Returns: {69954997999, 99889888998 }
481648713
9687381011
Returns: {481648713, 9687381011 }
80352110732
89988889999
Returns: {80352110732, 88999999999 }
496054236
89998988881
Returns: {496054236, 88999999999 }
48164828
82817020443
Returns: {48164828, 82817020443 }
9235547312
11458482217
Returns: {9235547312, 9999999999 }
41661126878
92225902584
Returns: {42000000000, 92225902584 }
44154453
71081469525
Returns: {44154453, 69999999999 }
208015600
6889888988
Returns: {400000000, 6889888988 }
8133863
69888999999
Returns: {8133863, 69888999999 }
429972385
964727183
Returns: {429972385, 964727183 }
81304265331
89888889999
Returns: {81304265331, 88999999999 }
3655615
9066855
Returns: {4000000, 9066855 }
688888988
100000000000
Returns: {688888988, 99999999999 }
45678720
88999989
Returns: {45680000, 88999989 }
98889989999
100000000000
Returns: {98889990000, 99999999999 }
49384313702
56667480040
Returns: {49384313702, 49899999999 }
68888899999
100000000000
Returns: {68889000000, 99999999999 }
2061144917
7008454496
Returns: {4000000000, 6999999999 }
9687250632
100000000000
Returns: {9687250632, 99999999999 }
323935956
955320240
Returns: {400000000, 955320240 }
88988888984
100000000000
Returns: {88988889000, 99999999999 }
1
51087104584
Returns: {4, 49899999999 }
42923371826
79821176964
Returns: {42924000000, 69999999999 }
1
14171601999
Returns: {4, 9999999999 }
8206020037
97766296592
Returns: {8206020037, 96999999999 }
189679
820545
Returns: {400000, 820545 }
69902853467
100000000000
Returns: {69902853467, 99999999999 }
1
63605856184
Returns: {4, 63605856184 }
81258387455
97115265770
Returns: {81258387455, 96999999999 }
1
68889899988
Returns: {4, 68889889999 }
89888889898
100000000000
Returns: {90000000000, 99999999999 }
3610318
4469468
Returns: {4000000, 4469468 }
99988988898
100000000000
Returns: {99988988898, 99999999999 }
2994408614
98889999988
Returns: {4000000000, 98889999988 }
47327965875
100000000000
Returns: {48000000000, 99999999999 }
1
69999989
Returns: {4, 69999988 }
51753396007
62179689257
Returns: {60000000000, 62169999999 }
1
9031190562
Returns: {4, 9031190562 }
73092357163
100000000000
Returns: {80000000000, 99999999999 }
4566051529
9052044783
Returns: {4566051529, 9052044783 }
54713114427
88085827318
Returns: {60000000000, 88085827318 }
1
42258971
Returns: {4, 42258971 }
96902303721
98330599023
Returns: {96902303721, 98289999999 }
4228298
6694169
Returns: {4228298, 6694169 }
88999988999
100000000000
Returns: {88999988999, 99999999999 }
1
8769874449
Returns: {4, 8769874449 }
39432443377
89647002085
Returns: {40000000000, 88999999999 }
1
69663
Returns: {4, 69663 }
63953098
100000000000
Returns: {63953098, 99999999999 }
1
6899899
Returns: {4, 6898999 }
899999999
100000000000
Returns: {900000000, 99999999999 }
28768
90536
Returns: {40000, 90536 }
88989999882
99983357380
Returns: {88989999882, 99983356999 }
9326792
9558352
Returns: {9326792, 9558352 }
75955122098
100000000000
Returns: {80000000000, 99999999999 }
829285736
968725063
Returns: {840000000, 968725063 }
99998899889
100000000000
Returns: {99998900000, 99999999999 }
33321816478
82528977370
Returns: {40000000000, 82528977370 }
90860076763
97305318322
Returns: {90860076763, 96999999999 }
1
628901833
Returns: {4, 628901833 }
19192884239
97377894585
Returns: {40000000000, 96999999999 }
738707691
814561972
Returns: {800000000, 814561972 }
22414068747
100000000000
Returns: {40000000000, 99999999999 }
1497319
9647151
Returns: {4000000, 9647151 }
96395943269
97228217540
Returns: {96395943269, 96999999999 }
1
63995587737
Returns: {4, 63995587737 }
70128096999
73206879859
Returns: { }
337781718
422589493
Returns: {400000000, 422589493 }
49668172455
100000000000
Returns: {49668200000, 99999999999 }
823430871
904450328
Returns: {824000000, 904450328 }
57675811768
58856631140
Returns: { }
1
5723473541
Returns: {4, 4989999999 }
53067181740
100000000000
Returns: {60000000000, 99999999999 }
1
820602003
Returns: {4, 820602003 }
98619696523
100000000000
Returns: {98619696523, 99999999999 }
1166787280
6899989998
Returns: {4000000000, 6898999989 }
99989889898
99992162353
Returns: {99990000000, 99992162353 }
1
89988889889
Returns: {4, 88999999999 }
49605423326
100000000000
Returns: {49605423326, 99999999999 }
23554513
88999899
Returns: {40000000, 88999899 }
688998889
100000000000
Returns: {689000000, 99999999999 }
94626389
98898889
Returns: {94626389, 98898888 }
10383612516
100000000000
Returns: {40000000000, 99999999999 }
57107486
80238609
Returns: {60000000, 80238609 }
79969793590
100000000000
Returns: {80000000000, 99999999999 }
1
9998888989
Returns: {4, 9998888988 }
50318863571
100000000000
Returns: {60000000000, 99999999999 }
1
40801006699
Returns: {4, 40800999999 }
49442045368
100000000000
Returns: {49442045400, 99999999999 }
52398993
95584955
Returns: {60000000, 95584955 }
42453340
100000000000
Returns: {42453340, 99999999999 }
1
903
Returns: {4, 903 }
69998999899
97741693254
Returns: {69999000000, 96999999999 }
1
95538
Returns: {4, 95538 }
72201731258
82203525061
Returns: {80000000000, 82203525061 }
1
898999988
Returns: {4, 889999999 }
98889989999
99082478043
Returns: {98889990000, 99082478043 }
742606762
820602003
Returns: {800000000, 820602003 }
5106712143
5723473541
Returns: { }
2
16
Returns: {4, 9 }
8769874449
8769874449
Returns: {8769874449, 8769874449 }
91922390943
91922390945
Returns: { }
1497319
1497319
Returns: { }
3610318
3610318
Returns: { }
9046220664
9052044783
Returns: {9046220664, 9052044783 }
89989999889
89989999896
Returns: { }
618
625
Returns: {620, 625 }
89989999889
98416187067
Returns: {90000000000, 98416186999 }
98286263642
98330599023
Returns: {98286263642, 98289999999 }
87333673274
87333673274
Returns: {87333673274, 87333673274 }
81
88
Returns: {81, 88 }
25782121
25782121
Returns: { }
81258387455
81258387455
Returns: {81258387455, 81258387455 }
867
868
Returns: {867, 868 }
919
932
Returns: {920, 932 }
40801006699
40801006699
Returns: { }
89989999880
89989999896
Returns: { }
3
5
Returns: {4, 4 }
9046220664
9046220664
Returns: {9046220664, 9046220664 }
91777769967
98898999989
Returns: {91777770000, 98898999988 }
5
5
Returns: { }
996221
996237
Returns: {996221, 996229 }
71081469525
71081469525
Returns: { }
47327965875
52292761073
Returns: {48000000000, 49899999999 }
69888898872
69888898889
Returns: {69888898872, 69888898889 }
88988988899
98150000965
Returns: {88988988900, 98150000965 }
99999999998
99999999998
Returns: {99999999998, 99999999998 }
99999999998
99999999999
Returns: {99999999998, 99999999999 }
99999999998
100000000000
Returns: {99999999998, 99999999999 }
99999999999
99999999999
Returns: {99999999999, 99999999999 }
99999999999
100000000000
Returns: {99999999999, 99999999999 }
100000000000
100000000000
Returns: { }
10000000000
40000000000
Returns: {40000000000, 40000000000 }
10000000000
39999999999
Returns: { }
9999999999
39999999999
Returns: {9999999999, 9999999999 }
10000000000
100000000000
Returns: {40000000000, 99999999999 }
50000000000
79999999999
Returns: {60000000000, 69999999999 }
9405471139
28553001143
Returns: {9405480000, 9999999999 }
8343274211
9374342342
Returns: {8400000000, 9369999999 }
57331
111917
Returns: {60000, 99999 }