10311 - Goldbach and Euler

All about problems in Volume 103. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Rivaldo
New poster
Posts: 19
Joined: Sun Jul 07, 2002 3:59 pm

Post by Rivaldo »

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

mmammel
New poster
Posts: 11
Joined: Fri Aug 23, 2002 9:42 pm
Location: MD, USA
Contact:

Post by mmammel »

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

Post by Alexandru Mosoi »

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?

Post by Alexandru Mosoi »

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:

Post by Picard »

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)

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

10 secs limit - a kiler

Post by scythe »

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 - 8)

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

This problem is hell

Post by scythe »

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 :o

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

Post by minhaz »

:roll:
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]

:o
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

Post by Jucovschi Constantin »

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
Location: BANGLADESH
Contact:

Post by Jalal »

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 :wink:

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

Re: How to make 10311 run under 10s

Post by Jalal »

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............. 8)
But u cant write the method of ur algorithm then posters can give idea to
improve ur code........... :lol:

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

What's wrong

Post by jpfarias »

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

Post by jpfarias »

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:

Post by Dominik Michniewski »

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

Post by Eric »

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

Post Reply

Return to “Volume 103 (10300-10399)”