OJ Board

It's very obvious that i forgot i had moved it. I'm sorry! Thanks a lot!

I must have some problem reading input -- the program works fine on my PC, but I get "Output limit exceeded" with the judge. Even if my program is slow it should not get that message! It must get stuck in some kind of loop when it reads the input. Here is how I read:

I'm using Fermat's little theorem to check the primality of a given number.
In order not to have problems with pseudoprime numbers, I also made a list with them (I took it from the Internet). So, every time I found a number that can be prime I check the list. If the list contains that number then that number is not prime.

To be sure of the corectitude of the program I made a similar program that uses the classical method of checking if a given number is eighter prime or not. Although my program seems to be correct I still get WA. Why??

I posted my program, so you can compare with yours (if you want). Thanks.

#include <stdio.h>
#include <stdlib.h>

#define pseudoprime_count 2058
int pseudoprime_list[pseudoprime_count] =
{
341, 561, 645, 1105, 1387, 1729, 1905, 2047,
2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681,
5461, 6601, 7957, 8321, 8481, 8911, 10261, 10585,
11305, 12801, 13741, 13747, 13981, 14491, 15709, 15841,
16705, 18705, 18721, 19951, 23001, 23377, 25761, 29341,
30121, 30889, 31417, 31609, 31621, 33153, 34945, 35333,
39865, 41041, 41665, 42799, 46657, 49141, 49981, 52633,
55245, 57421, 60701, 60787, 62745, 63973, 65077, 65281,
68101, 72885, 74665, 75361, 80581, 83333, 83665, 85489,
87249, 88357, 88561, 90751, 91001, 93961, 101101, 104653,
107185, 113201, 115921, 121465, 123251, 126217, 129889, 129921,
130561, 137149, 149281, 150851, 154101, 157641, 158369, 162193,
162401, 164737, 172081, 176149, 181901, 188057, 188461, 194221,
196021, 196093, 204001, 206601, 208465, 212421, 215265, 215749,
219781, 220729, 223345, 226801, 228241, 233017, 241001, 249841,
252601, 253241, 256999, 258511, 264773, 266305, 271951, 272251,
275887, 276013, 278545, 280601, 282133, 284581, 285541, 289941,
294271, 294409, 314821, 318361, 323713, 332949, 334153, 340561,
341497, 348161, 357761, 367081, 387731, 390937, 396271, 399001,
401401, 410041, 422659, 423793, 427233, 435671, 443719, 448921,
449065, 451905, 452051, 458989, 464185, 476971, 481573, 486737,
488881, 489997, 493697, 493885, 512461, 513629, 514447, 526593,
530881, 534061, 552721, 556169, 563473, 574561, 574861, 580337,
582289, 587861, 588745, 604117, 611701, 617093, 622909, 625921,
635401, 642001, 647089, 653333, 656601, 657901, 658801, 665281,
665333, 665401, 670033, 672487, 679729, 680627, 683761, 688213,
710533, 711361, 721801, 722201, 722261, 729061, 738541, 741751,
742813, 743665, 745889, 748657, 757945, 769567, 769757, 786961,
800605, 818201, 825265, 831405, 838201, 838861, 841681, 847261,
852481, 852841, 873181, 875161, 877099, 898705, 915981, 916327,
934021, 950797, 976873, 983401, 997633, 1004653, 1016801, 1018921,
1023121, 1024651, 1033669, 1050985, 1052503, 1052929, 1053761, 1064053,
1073021, 1082401, 1082809, 1092547, 1093417, 1104349, 1106785, 1109461,
1128121, 1132657, 1139281, 1141141, 1145257, 1152271, 1157689, 1168513,
1193221, 1194649, 1207361, 1246785, 1251949, 1252697, 1275681, 1277179,
1293337, 1302451, 1306801, 1325843, 1333333, 1357441, 1357621, 1373653,
1394185, 1397419, 1398101, 1419607, 1433407, 1441091, 1457773, 1459927,
1461241, 1463749, 1472065, 1472353, 1472505, 1485177, 1489665, 1493857,
1500661, 1507561, 1507963, 1509709, 1520905, 1529185, 1530787, 1533601,
1533961, 1534541, 1537381, 1549411, 1569457, 1579249, 1584133, 1608465,
1615681, 1620385, 1643665, 1678541, 1690501, 1711381, 1719601, 1730977,
1735841, 1746289, 1755001, 1773289, 1801969, 1809697, 1811573, 1815465,
1826203, 1827001, 1830985, 1837381, 1839817, 1840357, 1857241, 1876393,
1892185, 1896961, 1907851, 1908985, 1909001, 1937881, 1969417, 1987021,
1993537, 1994689, 2004403, 2008597, 2035153, 2077545, 2081713, 2085301,
2089297, 2100901, 2113665, 2113921, 2121301, 2134277, 2142141, 2144521,
2162721, 2163001, 2165801, 2171401, 2181961, 2184571, 2205967, 2213121,
2232865, 2233441, 2261953, 2264369, 2269093, 2284453, 2288661, 2290641,
2299081, 2304167, 2313697, 2327041, 2350141, 2387797, 2414001, 2419385,
2433601, 2434651, 2455921, 2487941, 2491637, 2503501, 2508013, 2510569,
2513841, 2528921, 2531845, 2537641, 2603381, 2609581, 2615977, 2617451,
2626177, 2628073, 2649029, 2649361, 2670361, 2704801, 2719981, 2722681,
2746477, 2746589, 2748023, 2757241, 2773981, 2780731, 2793351, 2797921,
2811271, 2827801, 2867221, 2880361, 2882265, 2899801, 2909197, 2921161,
2940337, 2944261, 2953711, 2976487, 2977217, 2987167, 3020361, 3048841,
3057601, 3059101, 3073357, 3090091, 3094273, 3116107, 3125281, 3146221,
3165961, 3181465, 3186821, 3224065, 3225601, 3235699, 3316951, 3336319,
3337849, 3345773, 3363121, 3370641, 3375041, 3375487, 3400013, 3413533,
3429037, 3435565, 3471071, 3539101, 3542533, 3567481, 3568661, 3581761,
3605429, 3656449, 3664585, 3679201, 3726541, 3746289, 3755521, 3763801,
3779185, 3814357, 3828001, 3898129, 3911197, 3916261, 3936691, 3985921,
4005001, 4014361, 4025905, 4038673, 4069297, 4072729, 4082653, 4097791,
4101637, 4151869, 4154161, 4154977, 4181921, 4188889, 4209661, 4229601,
4259905, 4314967, 4335241, 4360621, 4361389, 4363261, 4371445, 4415251,
4463641, 4469471, 4480477, 4502485, 4504501, 4513841, 4535805, 4567837,
4613665, 4650049, 4670029, 4682833, 4698001, 4706821, 4714201, 4767841,
4806061, 4827613, 4835209, 4863127, 4864501, 4868701, 4869313, 4877641,
4895065, 4903921, 4909177, 4917331, 4917781, 4922413, 4974971, 4984001,
5016191, 5031181, 5034601, 5044033, 5049001, 5095177, 5131589, 5133201,
5148001, 5173169, 5173601, 5176153, 5187637, 5193721, 5250421, 5256091,
5258701, 5271841, 5284333, 5310721, 5351537, 5400489, 5423713, 5444489,
5456881, 5481451, 5489121, 5489641, 5524693, 5529745, 5545145, 5551201,
5560809, 5575501, 5590621, 5599765, 5632705, 5672041, 5681809, 5733649,
5758273, 5766001, 5804821, 5859031, 5872361, 5919187, 5968261, 5968873,
5977153, 6027193, 6049681, 6054985, 6118141, 6122551, 6135585, 6140161,
6159301, 6183601, 6189121, 6212361, 6226193, 6233977, 6235345, 6236257,
6236473, 6242685, 6255341, 6278533, 6309901, 6313681, 6334351, 6350941,
6368689, 6386993, 6474691, 6539527, 6617929, 6628385, 6631549, 6658669,
6732817, 6733693, 6749021, 6779137, 6787327, 6836233, 6840001, 6868261,
6886321, 6912079, 6952037, 6955541, 6973057, 6973063, 6998881, 7008001,
7017193, 7040001, 7177105, 7207201, 7215481, 7232321, 7233265, 7259161,
7273267, 7295851, 7306261, 7306561, 7414333, 7416289, 7428421, 7429117,
7455709, 7462001, 7516153, 7519441, 7546981, 7656721, 7674967, 7693401,
7724305, 7725901, 7759937, 7803769, 7808593, 7814401, 7820201, 7883731,
7995169, 8012845, 8036033, 8041345, 8043841, 8095447, 8134561, 8137585,
8137633, 8180461, 8209657, 8231653, 8239477, 8280229, 8321671, 8322945,
8341201, 8355841, 8362201, 8384513, 8388607, 8462233, 8534233, 8640661,
8646121, 8650951, 8656705, 8719309, 8719921, 8725753, 8727391, 8745277,
8812273, 8830801, 8902741, 8916251, 8927101, 8992201, 9006401, 9037729,
9040013, 9046297, 9056501, 9063105, 9069229, 9073513, 9084223, 9106141,
9131401, 9143821, 9223401, 9224391, 9273547, 9345541, 9371251, 9439201,
9480461, 9494101, 9533701, 9564169, 9567673, 9582145, 9585541, 9588151,
9591661, 9613297, 9638785, 9692453, 9724177, 9729301, 9774181, 9816465,
9834781, 9863461, 9890881, 9908921, 9920401, 9995671, 10004681, 10024561,
10031653, 10033777, 10079521, 10084177, 10134601, 10185841, 10226161, 10239985,
10251473, 10266001, 10267951, 10275685, 10317601, 10323769, 10331141, 10386241,
10393201, 10402237, 10402561, 10403641, 10425511, 10505701, 10513261, 10545991,
10606681, 10610063, 10635751, 10655905, 10680265, 10700761, 10712857, 10763653,
10802017, 10818505, 10837321, 10877581, 10956673, 10958221, 10974385, 10974881,
11034365, 11075857, 11081459, 11115037, 11119105, 11157721, 11205601, 11242465,
11328409, 11335501, 11367137, 11433301, 11473885, 11541307, 11585293, 11592397,
11644921, 11767861, 11776465, 11777599, 11875821, 11921001, 11972017, 12032021,
12067705, 12096613, 12261061, 12262321, 12263131, 12273769, 12322133, 12327121,
12376813, 12407011, 12490201, 12498061, 12584251, 12599233, 12643381, 12659989,
12702145, 12711007, 12757361, 12783811, 12854437, 12932989, 12936763, 12939121,
12945745, 12979765, 13057787, 13073941, 13187665, 13216141, 13295281, 13333441,
13338371, 13357981, 13421773, 13446253, 13448593, 13500313, 13554781, 13635289,
13635649, 13694761, 13696033, 13747361, 13757653, 13773061, 13823601, 13838569,
13856417, 13899565, 13942081, 13971841, 13991647, 13992265, 13996951, 14012797,
14026897, 14154337, 14179537, 14282143, 14324473, 14469841, 14556081, 14589901,
14609401, 14671801, 14676481, 14684209, 14709241, 14794081, 14796289, 14865121,
14870801, 14885697, 14892153, 14898631, 14899751, 14913991, 14980411, 15082901,
15101893, 15124969, 15139199, 15162941, 15188557, 15207361, 15220951, 15247621,
15248773, 15268501, 15403285, 15472441, 15479777, 15510041, 15525241, 15560461,
15583153, 15603391, 15621409, 15698431, 15700301, 15716041, 15732721, 15757741,
15802681, 15829633, 15888313, 15913261, 15976747, 15978007, 16046641, 16053193,
16070429, 16132321, 16149169, 16149601, 16153633, 16158331, 16263105, 16324001,
16349477, 16360381, 16435747, 16539601, 16666651, 16705021, 16717061, 16773121,
16778881, 16818877, 16822081, 16843009, 16853077, 16879501, 16973393, 16998961,
17020201, 17098369, 17116837, 17134043, 17208601, 17236801, 17316001, 17327773,
17375249, 17405537, 17429861, 17450569, 17509501, 17585969, 17586361, 17590957,
17641207, 17698241, 17759681, 17777191, 17812081, 17870561, 17895697, 18003349,
18007345, 18067501, 18073817, 18137505, 18151861, 18162001, 18300241, 18307381,
18366937, 18443701, 18454921, 18468901, 18487267, 18490381, 18535177, 18541441,
18595801, 18607009, 18653353, 18736381, 18740971, 18779761, 18900973, 18985627,
19020191, 19054933, 19092921, 19149571, 19260865, 19328653, 19384289, 19404139,
19471033, 19523505, 19569265, 19607561, 19683001, 19734157, 19781763, 19985269,
20081953, 20099017, 20117467, 20140129, 20202481, 20234341, 20261251, 20417311,
20489239, 20494401, 20626165, 20647621, 20770621, 20964961, 20968501, 21042001,
21224401, 21303343, 21306157, 21355951, 21359521, 21397381, 21400481, 21414169,
21417991, 21459361, 21474181, 21559741, 21584305, 21585313, 21623659, 21654533,
21715681, 21789901, 21814417, 21880801, 21907009, 22066201, 22075579, 22087477,
22137809, 22203181, 22215961, 22269745, 22351249, 22369621, 22397497, 22432201,
22480381, 22487101, 22509691, 22513457, 22564081, 22591301, 22665505, 22669501,
22711873, 22848541, 22849481, 22885129, 22899097, 22953673, 23054601, 23247901,
23261713, 23283037, 23286781, 23315977, 23382529, 23386441, 23405341, 23464033,
23517985, 23577497, 23634181, 23734901, 23736385, 23808721, 23822329, 23828017,
23872213, 23963869, 23966011, 24037021, 24158641, 24161905, 24214051, 24356377,
24726773, 24776557, 24904153, 24913681, 24929281, 25080101, 25150501, 25266745,
25270105, 25276421, 25326001, 25457833, 25520833, 25540291, 25557121, 25603201,
25629913, 25640641, 25696133, 25768261, 25831585, 25840081, 25846913, 25873381,
25909453, 25947959, 26254801, 26280073, 26296401, 26377921, 26465089, 26470501,
26474581, 26553241, 26634301, 26719701, 26758057, 26813221, 26821601, 26840269,
26877421, 26886817, 26921089, 26932081, 26977001, 27032545, 27062101, 27108397,
27118601, 27128201, 27168337, 27218269, 27219697, 27271151, 27279409, 27331921,
27336673, 27380831, 27392041, 27401401, 27402481, 27409541, 27476641, 27491237,
27492581, 27509653, 27600001, 27664033, 27700609, 27714961, 27736345, 27798461,
27808463, 27846721, 27966709, 27986421, 28011001, 28029001, 28071121, 28172629,
28175001, 28312921, 28325881, 28406953, 28449961, 28527049, 28572961, 28629613,
28717483, 28787185, 29020321, 29111881, 29137021, 29143633, 29214541, 29581501,
29593159, 29732221, 29878381, 30022129, 30058381, 30069721, 30090817, 30185569,
30219757, 30295141, 30296761, 30338593, 30388753, 30411201, 30418957, 30529693,
30576151, 30653245, 30662497, 30718441, 30739969, 30740417, 30881551, 30894307,
30951181, 30958201, 30971161, 30992401, 30996001, 31040833, 31118221, 31146661,
31150351, 31166803, 31198693, 31405501, 31436123, 31692805, 31735621, 31759121,
31766983, 31794241, 31880577, 32080651, 32091781, 32095057, 32158621, 32168117,
32264029, 32285041, 32368609, 32428045, 32497921, 32676481, 32701297, 32756581,
32899201, 32914441, 33018985, 33146717, 33193117, 33298337, 33302401, 33408145,
33596641, 33600533, 33627301, 33704101, 33840397, 33848311, 33872593, 33965261,
34003061, 34043101, 34100821, 34111441, 34124641, 34196401, 34386121, 34487601,
34540801, 34581457, 34603041, 34657141, 34856167, 34890481, 34901461, 34944001,
35428141, 35498467, 35571601, 35576599, 35626501, 35703361, 35820937, 35851037,
35926801, 35932441, 35967921, 35976721, 36121345, 36168265, 36255451, 36291193,
36307981, 36338653, 36354449, 36448387, 36507801, 36721021, 36724591, 36765901,
36852481, 36861901, 36919681, 36942157, 36974341, 36981601, 37109467, 37167361,
37280881, 37354465, 37376509, 37439201, 37469701, 37491301, 37695505, 37727341,
37769887, 37938901, 37962541, 37964809, 37988497, 38010307, 38046817, 38118763,
38151361, 38171953, 38210323, 38239741, 38342071, 38404501, 38439523, 38453151,
38560861, 38584801, 38624041, 38637361, 38789913, 38790753, 38801089, 38903287,
38971661, 39016741, 39052333, 39117439, 39126313, 39353665, 39465091, 39467377,
39512773, 39573073, 39655153, 39684157, 39789841, 40094341, 40160737, 40165093,
40238797, 40280065, 40315441, 40325041, 40361197, 40374901, 40430401, 40622401,
40629601, 40778989, 40782589, 40801861, 40827473, 40841821, 40886241, 40917241,
40928701, 40933705, 40987201, 41017681, 41067665, 41073241, 41102601, 41121433,
41262073, 41298985, 41341321, 41396921, 41424801, 41471521, 41541241, 41568101,
41590297, 41604109, 41607721, 41642681, 41662297, 41840809, 41866001, 41987111,
42009217, 42344609, 42485119, 42490801, 42623017, 42689305, 42694279, 42697873,
42702661, 42709591, 42763501, 42984589, 42998901, 43039501, 43136821, 43224397,
43235641, 43286881, 43331401, 43363601, 43397551, 43584481, 43620409, 43661257,
43798457, 43914949, 44070841, 44081101, 44238481, 44314129, 44347381, 44465221,
44472001, 44482901, 44521301, 44671001, 44695211, 44731051, 44823241, 44824501,
44912701, 44953441, 44963029, 45100177, 45175201, 45219329, 45318561, 45393601,
45414433, 45485881, 45563027, 45593065, 45769645, 45819541, 45830161, 45877861,
45879941, 45890209, 46045117, 46055851, 46094401, 46104697, 46256489, 46282405,
46325029, 46386589, 46469809, 46483633, 46517857, 46647745, 46657181, 46679761,
46860001, 46878601, 47006785, 47063611, 47220367, 47253781, 47349373, 47356171,
47647117, 47734141, 47744209, 47759041, 47903701, 47918581, 47930023, 47953621,
48064021, 48191653, 48269761, 48277081, 48316321, 48316969, 48321001, 48369727,
48398065, 48400753, 48448661, 48462301, 48506581, 48551161, 48563089, 48592393,
48628801, 48650641, 48656869, 49075417, 49084321, 49303801, 49333201, 49411801,
49430305, 49439237, 49459801, 49472281, 49664207, 50155733, 50176477, 50193793,
50201089, 50376019, 50443201, 50473501, 50523661, 51030601, 51129781, 51283501,
51302353, 51340807, 51396865, 51500521, 51509161, 51627817, 51803821, 51890545,
52018341, 52072021, 52119289, 52142221, 52181407, 52204237, 52365457, 52452905,
52869601, 53154337, 53245921, 53283169, 53315605, 53399449, 53542147, 53560801,
53656021, 53661945, 53675623, 53695721, 53711113, 53728921, 53795521, 54029741,
54060721, 54177949, 54215161, 54448153, 54449431, 54468001, 54545821, 54651961,
54767881, 54772381, 55035001, 55109401, 55176097, 55200181, 55318957, 55324801,
55329985, 55462177, 55610837, 55729957, 55961065, 56052361, 56420033, 56479897,
56608201, 56643181, 56669041, 56687821, 56810137, 57130161, 57172501, 57421219,
57561085, 57707209, 57749185, 57762433, 58003213, 58422409, 58449847, 58489201,
58498105, 58509977, 58679941, 58708761, 58755877, 58903741, 59408497, 59426221,
59469697, 59586241, 59589973, 59631211, 59840537, 59913157, 59953741, 59955331,
59999011, 60112885, 60155201, 60352921, 60375745, 60514129, 60547831, 60558841,
60566431, 60581401, 60696661, 60738257, 60761701, 60769051, 60925879, 60957361,
60998653, 61198921, 61201009, 61219789, 61309333, 61330291, 61377109, 61679905,
61754941, 61755751, 61794709, 61832377, 62176661, 62248649, 62289541, 62490901,
62633371, 62656985, 62756641, 63001801, 63002501, 63065281, 63127681, 63167743,
63294553, 63318169, 63328469, 63337393, 63346999, 63388033, 63526519, 63560685,
63729073, 63781901, 63884521, 63919801, 64009261, 64148717, 64162693, 64238021,
64377991, 64477249, 64567405, 64605041, 64644385, 64685545, 64735897, 64774081,
64940041, 65037817, 65144501, 65241793, 65254393, 65301013, 65350801, 65350821,
65359477, 65427701, 65523781, 65565457, 65919745, 66024901, 66096253, 66296401,
66384121, 66437841, 66760471, 66790057, 66849091, 66886417, 66932851, 66976273,
66977281, 67194401, 67213801, 67371265, 67529437, 67541761, 67559383, 67642513,
67653433, 67763803, 67902031, 67928221, 67940449, 67968385, 67994641, 68033801,
68075177, 68102641, 68154001, 68165761, 68275873, 68512867, 68621701, 68776561,
68800501, 68830021, 68839597, 68958681, 69030901, 69128641, 69176647, 69228967,
69231061, 69331969, 69414301, 69485281, 69612061, 69615793, 69678307, 69705529,
69741001, 69776785, 69885649, 69917371, 70006021, 70030501, 70147561, 70149631,
70195501, 70461331, 70463489, 70484065, 70488001, 70541099, 70561921, 70593931,
70626301, 70695769, 70728121, 70938429, 71040561, 71079661, 71107681, 71479765,
71570017, 71572957, 71711839, 71734417, 71804161, 72108421, 72135505, 72192021,
72286501, 72348409, 72498253, 72543547, 72595951, 72680431, 72734041, 72803809,
72805981, 72884701, 72887585, 73346365, 73439185, 73451665, 73522051, 73562833,
73645001, 73721341, 73988641, 74165065, 74193769, 74217487, 74329399, 74411131,
74658629, 74698345, 74705401, 74874869, 74927161, 74945953, 75140137, 75143251,
75151441, 75187669, 75501793, 75565873, 75676861, 75681541, 75765313, 75836905,
75927853, 76595761, 76704433, 76725091, 76745101, 76923461, 76969621, 77082545,
77295961, 77334769, 77442905, 77477401, 77518981, 77533123, 77576401, 77594653,
77648941, 77812153, 77817979, 77826001, 77858221, 78073801, 78091201, 78120001,
78206917, 78397705, 78526729, 78671651, 78795181, 78844801, 78905989, 78939089,
79398901, 79411201, 79417801, 79464533, 79525261, 79539197, 79624621, 79625701,
79739713, 79786523, 79854409, 79895401, 80142761, 80146909, 80282161, 80375707,
80556337, 80687881, 80787421, 80891009, 80918281, 80927821, 81189433, 81433591,
81445585, 81480601, 81612105, 81638401, 81680941, 81722145, 81789301, 81926461,
81954133, 82023649, 82139471, 82219801, 82268033, 82273201, 82279741, 82416101,
82452061, 82506439, 82847001, 82870517, 82882753, 82929001, 82976181, 82995421,
83058481, 83083001, 83099521, 83103329, 83204801, 83814151, 83966401, 84028407,
84164033, 84234745, 84311569, 84350561, 84375761, 84417985, 84421081, 84487457,
84758389, 84809521, 84998503, 85030921, 85207669, 85328717, 85374577, 85400701,
85519337, 85759147, 85761481, 85823401, 85875361, 86027329, 86067241, 86114117,
86204977, 86438857, 86484269, 86530621, 86559045, 86968981, 86999837, 87211573,
87318001, 87483241, 87499651, 87558127, 87571121, 87694261, 88099339, 88123141,
88256449, 88368853, 88407361, 88466521, 88615801, 88661861, 88689601, 88735921,
88930463, 89148417, 89244901, 89308771, 89670001, 89784581, 89816545, 89896717,
89915365, 89961421, 90014653, 90270613, 90278161, 90341197, 90532141, 90626185,
90665789, 90670861, 90698401, 90803429, 91367431, 91433281, 91453705, 91587289,
91659283, 92027001, 92139433, 92343745, 92438581, 92625121, 92631001, 92645437,
92677273, 92829781, 92974921, 93030145, 93431521, 93473953, 93541537, 93571633,
93591721, 93614521, 93643201, 93677761, 93839201, 93845161, 93869665, 93926197,
93967105, 94316401, 94502701, 94536001, 94790401, 95053249, 95200561, 95423329,
95451361, 95452781, 96135601, 96259681, 96271681, 96386865, 96589585, 96618397,
96653985, 96791881, 96888641, 96895441, 96904081, 96916279, 96925921, 97047301,
97255801, 97420141, 97487785, 97496449, 97655933, 97676723, 97796953, 97863529,
97924217, 98124481, 98523877, 98586541, 98602381, 98735209, 98756281, 99036001,
99115297, 99486889, 99551881, 99789673, 99830641, 99861985, 99898801, 99945007,
99971821, 100017223,
};

#define prime_count 6542
int prime_list[prime_count];

int prime(int x, int sx)
{
if(x == 2) return 1;
if((x & 1) == 0) return 0;

for(int i = 3; i <= sx; i += 2)
if(x % i == 0) return 0;

return 1;
}

int cmp_int(const void *a, const void *b)
{
return *(int *)a - *(int *)b;
}

int prime(int x)
{
if(x == 1 || x == 2) return 1;
if((x & 1) == 0) return 0;

if(x < 65536) return bsearch(&x, prime_list, prime_count, sizeof(int), cmp_int) != NULL;

long long k = 2;
int found = 0;
for(int i = 30; i >= 0; i --)
{
if(found) k *= k;
if((x - 1) & (1 << i))
{
k *= (found + 1);
found = 1;
}
k %= x;
}

if(k == 1) return bsearch(&x, pseudoprime_list, pseudoprime_count, sizeof(int), cmp_int) == NULL;
return 0;
}

void print(int x, int y1, int y2, int found)
{
if(y1 > y2)
{
int tmp = y1;
y1 = y2; y2 = tmp;
}

if(found) printf("%d is the sum of %d and %d.\n", x, y1, y2);
else printf("%d is not the sum of two primes!\n", x);
}

int n, p;

int main(void)
{
// freopen("p10311.in", "rt", stdin);
// freopen("p10311.out", "wt", stdout);

// generam toate numerele prime pana la 65535(inclusiv)

n = 3, p = 2;
int count = 1;
prime_list[0] = 2;

for(; n < 65536; n += 2)
{
if(p * p <= n) p ++;
if(prime(n, p)) prime_list[count ++] = n;
}

// acum incepe rezolvarea efectiva a problemei

while(scanf("%d", &n) == 1)
{
if(n & 1)
{
print(n, 2, n - 2, prime(n - 2));
continue;
}

int found = 0;
p = n - (n >> 1);

while(p < n && !found)
{
if(prime(p) && prime(n - p)) found = 1;
else p ++;
}

print(n, n - p, p, found);
}

// fclose(stdin);
// fclose(stdout);
}[cpp][/cpp]

Sorry, I considered that 1 is prime. But still WA... Why?

please next time read the previous topics about the problem you are asking! you may found the answer there.

when taking the sum of two numbers, their difference should be positive, i. e. means >0. example 26 = 7+19 (not 13+13)

Well, i tried to solve the problem all day and finally (after a lot of attempts) i got ac. The problem is that UVA's new TL of 10 secs is very tight. (my time was 9.860)
To speed-up the primality tests, I use an eratostene's sieve for numbers up to 50010000, and Miller-Rabin for larger numbers.
Miller-Rabin only worked with 4 probes (cormen style). 3 was WA, 5 was TLE -

Well, after i got ac, i tried to optimize something and i got TLE. I tried the program which got ac and it got TLE and i can't manage to make it work in time (even with only 1 miller test).
This is weird

hello i got time limit exit in solving that problem and the answer of the judge is as follows


Your program has used more time (10.020 seconds) than the maximum
allowed for this problem by this judge (10 seconds).
[/quote]


can anyone help me how can i make the problem effiently solve.I add my source code here

[c]

#include<stdio.h>
#include<string.h>
#include<math.h>

#define size 8000000

char prime[size];

void main()
{
long int i,j,k,n,m;

memset(prime,0,size);
prime[0]=1,prime[1]=1,k=2;
for(i=2;i<=sqrt(size);)
{
if(!prime)
{
m=k;
for(j=k*i;j<size;j=i*(++k))
prime[j]=1;
k=m++;
}
if(i==2)
i++;
else
i+=2;
}
while(scanf("%ld",&n)==1)
{
if(prime[n]==0 || n<4)
printf("%ld is not the sum of two primes!\n",n);
else if(n==4)
printf("4 is the sum of 2 and 2.\n");
else
{
i=n/2;
if(i%2==0)
i--;
for(;i>2;i-=2)
if(!prime)
break;
for(;i>2;i-=2)
{
if(i<=n-i)
{
j=n-i;
if(!prime && !prime[j])
break;
}
else
break;
}
printf("%ld is the sum of %ld and %ld.\n",n,i,j);
}
}
}



it is really tough to attain the time 10 second

[/c]

Hi,

How to generate all prime numbers in interval 2-50.000.000 fastly ? I can do it in almost 8 sec but it's not enough.

Or how to solve the problem in 10 sec ?

scythe!
You may got accepted nearby 10sec. Sometime its happens.
If there is too much code submitted to judge then the jusge system can
be slow. ANd if u submit it when it dont have too much code then its can
be run quicker than the other time. ANd thats why this happen.
I think if u follow some technics u can avoid this for this prob.
One of that is there is just 1 prime which is even and that is 2.
so, first test (n-2) is a prime or not. Then the other things.
Hope can help

suctg wrote:Any ideas o the posted codes. I still can't do it under 10s. Posted codes don not help as they too have TLE Problems. IF anyone did solve the problem then please show the problem on the posted code below or post your code that runs under 10s.

Its not a better idea to post whole code on the board.............
But u cant write the method of ur algorithm then posters can give idea to
improve ur code...........

Hi!

I got WA in 8 sec.... But's still a WA...

Can anyone see what's wrong?

[cpp]

#include <stdio.h>
#include <string.h>
#include <math.h>

#define MAXSIEVE 100000000 // All prime numbers up to this
#define MAXSIEVEHALF (MAXSIEVE/2)
#define MAXSQRT 5000 // sqrt(MAXSIEVE)/2
char a[MAXSIEVE/16+2];
#define isprime(n) (a[(n)>>4]&(1<<(((n)>>1)&7))) // Works when n is odd

void init() {
int i,j;
memset(a,255,sizeof(a));
a[0]=0xFE;
for(i=1;i<MAXSQRT;i++) {
if (a[i>>3]&(1<<(i&7))) {
for(j=i+i+i+1;j<MAXSIEVEHALF;j+=i+i+1) {
a[j>>3]&=~(1<<(j&7));
}
}
}
}

int main() {
init();
int n;
while (scanf("%d", &n) == 1) {
if (n < 3) {
printf("%d is not the sum of two primes!\n", n);
}
if (n & 1) {
if (isprime(n-2)) {
printf("%d is the sum of 2 and %d.\n", n, n-2);
} else {
printf("%d is not the sum of two primes!\n", n);
}
} else {
bool ok = false;
for (int i=3; i<n/2+1; i+=2) {
if (isprime(i) && isprime(n-i)) {
printf("%d is the sum of %d and %d.\n", n, i, n-i);
ok = true;
break;
}
}
if (!ok) {
printf("%d is not the sum of two primes!\n", n);
}
}
}
return 0;
}


[/cpp]

Thanks!

JP!

Forget it!

It's solved!

I've forgot that (p2-p1) should be minimized....

Just replace i=3 .. n/2+1 to n/2+1 ... 3 on my solution to get AC, hehe!

JP

to suctg and shahriar mazoor:
maybe better is not rejudge all submissions, but set time limit for this problem to more than 10 secs ?I think, that it's only mistake, so I see and got accepted other problems with time-limit more than 10 secs (and time-limit for other are still 10)

DM

Oh...suctg.
Your program runs 10.014 doesn't mean that it can really finish in that time.
It is only the judge computer terminate your program immediately after 10s.
it doesn't mean your program finish time.