## 10311 - Goldbach and Euler

Moderator: Board moderators

Rivaldo
New poster
Posts: 19
Joined: Sun Jul 07, 2002 3:59 pm
It's very obvious that i forgot i had moved it. I'm sorry! Thanks a lot!

mmammel
New poster
Posts: 11
Joined: Fri Aug 23, 2002 9:42 pm
Location: MD, USA
Contact:
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:

Code: Select all

``````int val, l1;
char ch[32];

do
{ //loop
val=0;
l1=0;

gets(ch);
l1=strlen(ch);

if (l1)
{

for (i=0; i<l1; i++)
if (ch[i]>='0' && ch[i]<='9')
val=10*val+(int)(ch[i]-48);

...blah blah blah...

} //l1

} while (l1); //loop
``````

Alexandru Mosoi
New poster
Posts: 5
Joined: Wed Feb 20, 2002 2:00 am

### 10311 - Why do I get WA??

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]

Alexandru Mosoi
New poster
Posts: 5
Joined: Wed Feb 20, 2002 2:00 am

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

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

Picard
Learning poster
Posts: 96
Joined: Mon Jun 24, 2002 1:22 pm
Location: Hungary
Contact:

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

scythe
New poster
Posts: 12
Joined: Mon Oct 07, 2002 12:25 pm

### 10 secs limit - a kiler

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 -

scythe
New poster
Posts: 12
Joined: Mon Oct 07, 2002 12:25 pm

### This problem is hell

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

minhaz
New poster
Posts: 5
Joined: Sat Oct 19, 2002 4:20 am
Contact:

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]

Jucovschi Constantin
New poster
Posts: 9
Joined: Sat Oct 26, 2002 6:30 pm

### Primality Tests

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 ?

Jalal
Learning poster
Posts: 65
Joined: Sun Jun 02, 2002 8:41 pm
Contact:
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

Jalal
Learning poster
Posts: 65
Joined: Sun Jun 02, 2002 8:41 pm
Contact:

### Re: How to make 10311 run under 10s

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...........

jpfarias
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:

### What's wrong

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!

jpfarias
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:

### Forget it

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

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
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
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Eric
Learning poster
Posts: 83
Joined: Wed Sep 11, 2002 6:28 pm
Location: Hong Kong
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.