Boost-Commit :

Date view	Thread view	Subject view	Author view

From: gautamcool88_at_[hidden]
Date: 2008-09-02 14:42:32

Next message: emil_at_[hidden]: "[Boost-commit] svn:boost r48543 - trunk/boost/exception"
Previous message: gautamcool88_at_[hidden]: "[Boost-commit] svn:boost r48541 - sandbox/SOC/2008/parrallel_math/libs/math/test"

Author: s.gautam
Date: 2008-09-02 14:42:31 EDT (Tue, 02 Sep 2008)
New Revision: 48542
URL: http://svn.boost.org/trac/boost/changeset/48542

Log:
prime factorization attempt at hypergeometric distribution.
Added:
sandbox/SOC/2008/parrallel_math/boost/math/distributions/gsoc_hypergeometric.hpp (contents, props changed)

Added: sandbox/SOC/2008/parrallel_math/boost/math/distributions/gsoc_hypergeometric.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/parrallel_math/boost/math/distributions/gsoc_hypergeometric.hpp 2008-09-02 14:42:31 EDT (Tue, 02 Sep 2008)
@@ -0,0 +1,3622 @@
+/*
+An attempt at calculating the PDF of Hypergeometric Distribution
+using prime factorization. Code does not follow some boost guidelines,
+contains lots of duplication and is not generic.
+*/
+
+#include <map>
+#include <boost/math/distributions/detail/common_error_handling.hpp>
+#include <boost/math/special_functions/gamma.hpp>
+#include <boost/math/special_functions/fpclassify.hpp>
+using namespace std;
+
+//table of primes
+boost::array <int,3245> prime_table;
+
+namespace boost { namespace math {
+ namespace detail {
+
+
+ template <class RealType>
+ RealType exponent_of_prime(RealType factorial, RealType prime) {
+ RealType exponent=0;
+ RealType temp=prime;
+ do {
+ exponent+=factorial/prime;
+ prime*=temp;
+ } while(prime<=factorial);
+ return exponent;
+ }
+
+ }
+
+ template <class RealType = int , class Policy = policies::policy<> >
+ class hypergeometric_distribution
+ {
+ public:
+ typedef RealType value_type;
+ typedef Policy policy_type;
+
+ hypergeometric_distribution(RealType r, RealType n,RealType N) // Constructor.
+ : m_r(r), m_n(n),m_N(N),m_gamma(false)
+ {
+ static const char* function = "boost::math::hypergeometric_distribution<%1%>::hypergeometric_distribution";
+ //prime_table of primes (till 30000)
+ // Check parameters
+prime_table[0]=2;
+prime_table[1]=3;
+prime_table[2]=5;
+prime_table[3]=7;
+prime_table[4]=11;
+prime_table[5]=13;
+prime_table[6]=17;
+prime_table[7]=19;
+prime_table[8]=23;
+prime_table[9]=29;
+prime_table[10]=31;
+prime_table[11]=37;
+prime_table[12]=41;
+prime_table[13]=43;
+prime_table[14]=47;
+prime_table[15]=53;
+prime_table[16]=59;
+prime_table[17]=61;
+prime_table[18]=67;
+prime_table[19]=71;
+prime_table[20]=73;
+prime_table[21]=79;
+prime_table[22]=83;
+prime_table[23]=89;
+prime_table[24]=97;
+prime_table[25]=101;
+prime_table[26]=103;
+prime_table[27]=107;
+prime_table[28]=109;
+prime_table[29]=113;
+prime_table[30]=127;
+prime_table[31]=131;
+prime_table[32]=137;
+prime_table[33]=139;
+prime_table[34]=149;
+prime_table[35]=151;
+prime_table[36]=157;
+prime_table[37]=163;
+prime_table[38]=167;
+prime_table[39]=173;
+prime_table[40]=179;
+prime_table[41]=181;
+prime_table[42]=191;
+prime_table[43]=193;
+prime_table[44]=197;
+prime_table[45]=199;
+prime_table[46]=211;
+prime_table[47]=223;
+prime_table[48]=227;
+prime_table[49]=229;
+prime_table[50]=233;
+prime_table[51]=239;
+prime_table[52]=241;
+prime_table[53]=251;
+prime_table[54]=257;
+prime_table[55]=263;
+prime_table[56]=269;
+prime_table[57]=271;
+prime_table[58]=277;
+prime_table[59]=281;
+prime_table[60]=283;
+prime_table[61]=293;
+prime_table[62]=307;
+prime_table[63]=311;
+prime_table[64]=313;
+prime_table[65]=317;
+prime_table[66]=331;
+prime_table[67]=337;
+prime_table[68]=347;
+prime_table[69]=349;
+prime_table[70]=353;
+prime_table[71]=359;
+prime_table[72]=367;
+prime_table[73]=373;
+prime_table[74]=379;
+prime_table[75]=383;
+prime_table[76]=389;
+prime_table[77]=397;
+prime_table[78]=401;
+prime_table[79]=409;
+prime_table[80]=419;
+prime_table[81]=421;
+prime_table[82]=431;
+prime_table[83]=433;
+prime_table[84]=439;
+prime_table[85]=443;
+prime_table[86]=449;
+prime_table[87]=457;
+prime_table[88]=461;
+prime_table[89]=463;
+prime_table[90]=467;
+prime_table[91]=479;
+prime_table[92]=487;
+prime_table[93]=491;
+prime_table[94]=499;
+prime_table[95]=503;
+prime_table[96]=509;
+prime_table[97]=521;
+prime_table[98]=523;
+prime_table[99]=541;
+prime_table[100]=547;
+prime_table[101]=557;
+prime_table[102]=563;
+prime_table[103]=569;
+prime_table[104]=571;
+prime_table[105]=577;
+prime_table[106]=587;
+prime_table[107]=593;
+prime_table[108]=599;
+prime_table[109]=601;
+prime_table[110]=607;
+prime_table[111]=613;
+prime_table[112]=617;
+prime_table[113]=619;
+prime_table[114]=631;
+prime_table[115]=641;
+prime_table[116]=643;
+prime_table[117]=647;
+prime_table[118]=653;
+prime_table[119]=659;
+prime_table[120]=661;
+prime_table[121]=673;
+prime_table[122]=677;
+prime_table[123]=683;
+prime_table[124]=691;
+prime_table[125]=701;
+prime_table[126]=709;
+prime_table[127]=719;
+prime_table[128]=727;
+prime_table[129]=733;
+prime_table[130]=739;
+prime_table[131]=743;
+prime_table[132]=751;
+prime_table[133]=757;
+prime_table[134]=761;
+prime_table[135]=769;
+prime_table[136]=773;
+prime_table[137]=787;
+prime_table[138]=797;
+prime_table[139]=809;
+prime_table[140]=811;
+prime_table[141]=821;
+prime_table[142]=823;
+prime_table[143]=827;
+prime_table[144]=829;
+prime_table[145]=839;
+prime_table[146]=853;
+prime_table[147]=857;
+prime_table[148]=859;
+prime_table[149]=863;
+prime_table[150]=877;
+prime_table[151]=881;
+prime_table[152]=883;
+prime_table[153]=887;
+prime_table[154]=907;
+prime_table[155]=911;
+prime_table[156]=919;
+prime_table[157]=929;
+prime_table[158]=937;
+prime_table[159]=941;
+prime_table[160]=947;
+prime_table[161]=953;
+prime_table[162]=967;
+prime_table[163]=971;
+prime_table[164]=977;
+prime_table[165]=983;
+prime_table[166]=991;
+prime_table[167]=997;
+prime_table[168]=1009;
+prime_table[169]=1013;
+prime_table[170]=1019;
+prime_table[171]=1021;
+prime_table[172]=1031;
+prime_table[173]=1033;
+prime_table[174]=1039;
+prime_table[175]=1049;
+prime_table[176]=1051;
+prime_table[177]=1061;
+prime_table[178]=1063;
+prime_table[179]=1069;
+prime_table[180]=1087;
+prime_table[181]=1091;
+prime_table[182]=1093;
+prime_table[183]=1097;
+prime_table[184]=1103;
+prime_table[185]=1109;
+prime_table[186]=1117;
+prime_table[187]=1123;
+prime_table[188]=1129;
+prime_table[189]=1151;
+prime_table[190]=1153;
+prime_table[191]=1163;
+prime_table[192]=1171;
+prime_table[193]=1181;
+prime_table[194]=1187;
+prime_table[195]=1193;
+prime_table[196]=1201;
+prime_table[197]=1213;
+prime_table[198]=1217;
+prime_table[199]=1223;
+prime_table[200]=1229;
+prime_table[201]=1231;
+prime_table[202]=1237;
+prime_table[203]=1249;
+prime_table[204]=1259;
+prime_table[205]=1277;
+prime_table[206]=1279;
+prime_table[207]=1283;
+prime_table[208]=1289;
+prime_table[209]=1291;
+prime_table[210]=1297;
+prime_table[211]=1301;
+prime_table[212]=1303;
+prime_table[213]=1307;
+prime_table[214]=1319;
+prime_table[215]=1321;
+prime_table[216]=1327;
+prime_table[217]=1361;
+prime_table[218]=1367;
+prime_table[219]=1373;
+prime_table[220]=1381;
+prime_table[221]=1399;
+prime_table[222]=1409;
+prime_table[223]=1423;
+prime_table[224]=1427;
+prime_table[225]=1429;
+prime_table[226]=1433;
+prime_table[227]=1439;
+prime_table[228]=1447;
+prime_table[229]=1451;
+prime_table[230]=1453;
+prime_table[231]=1459;
+prime_table[232]=1471;
+prime_table[233]=1481;
+prime_table[234]=1483;
+prime_table[235]=1487;
+prime_table[236]=1489;
+prime_table[237]=1493;
+prime_table[238]=1499;
+prime_table[239]=1511;
+prime_table[240]=1523;
+prime_table[241]=1531;
+prime_table[242]=1543;
+prime_table[243]=1549;
+prime_table[244]=1553;
+prime_table[245]=1559;
+prime_table[246]=1567;
+prime_table[247]=1571;
+prime_table[248]=1579;
+prime_table[249]=1583;
+prime_table[250]=1597;
+prime_table[251]=1601;
+prime_table[252]=1607;
+prime_table[253]=1609;
+prime_table[254]=1613;
+prime_table[255]=1619;
+prime_table[256]=1621;
+prime_table[257]=1627;
+prime_table[258]=1637;
+prime_table[259]=1657;
+prime_table[260]=1663;
+prime_table[261]=1667;
+prime_table[262]=1669;
+prime_table[263]=1693;
+prime_table[264]=1697;
+prime_table[265]=1699;
+prime_table[266]=1709;
+prime_table[267]=1721;
+prime_table[268]=1723;
+prime_table[269]=1733;
+prime_table[270]=1741;
+prime_table[271]=1747;
+prime_table[272]=1753;
+prime_table[273]=1759;
+prime_table[274]=1777;
+prime_table[275]=1783;
+prime_table[276]=1787;
+prime_table[277]=1789;
+prime_table[278]=1801;
+prime_table[279]=1811;
+prime_table[280]=1823;
+prime_table[281]=1831;
+prime_table[282]=1847;
+prime_table[283]=1861;
+prime_table[284]=1867;
+prime_table[285]=1871;
+prime_table[286]=1873;
+prime_table[287]=1877;
+prime_table[288]=1879;
+prime_table[289]=1889;
+prime_table[290]=1901;
+prime_table[291]=1907;
+prime_table[292]=1913;
+prime_table[293]=1931;
+prime_table[294]=1933;
+prime_table[295]=1949;
+prime_table[296]=1951;
+prime_table[297]=1973;
+prime_table[298]=1979;
+prime_table[299]=1987;
+prime_table[300]=1993;
+prime_table[301]=1997;
+prime_table[302]=1999;
+prime_table[303]=2003;
+prime_table[304]=2011;
+prime_table[305]=2017;
+prime_table[306]=2027;
+prime_table[307]=2029;
+prime_table[308]=2039;
+prime_table[309]=2053;
+prime_table[310]=2063;
+prime_table[311]=2069;
+prime_table[312]=2081;
+prime_table[313]=2083;
+prime_table[314]=2087;
+prime_table[315]=2089;
+prime_table[316]=2099;
+prime_table[317]=2111;
+prime_table[318]=2113;
+prime_table[319]=2129;
+prime_table[320]=2131;
+prime_table[321]=2137;
+prime_table[322]=2141;
+prime_table[323]=2143;
+prime_table[324]=2153;
+prime_table[325]=2161;
+prime_table[326]=2179;
+prime_table[327]=2203;
+prime_table[328]=2207;
+prime_table[329]=2213;
+prime_table[330]=2221;
+prime_table[331]=2237;
+prime_table[332]=2239;
+prime_table[333]=2243;
+prime_table[334]=2251;
+prime_table[335]=2267;
+prime_table[336]=2269;
+prime_table[337]=2273;
+prime_table[338]=2281;
+prime_table[339]=2287;
+prime_table[340]=2293;
+prime_table[341]=2297;
+prime_table[342]=2309;
+prime_table[343]=2311;
+prime_table[344]=2333;
+prime_table[345]=2339;
+prime_table[346]=2341;
+prime_table[347]=2347;
+prime_table[348]=2351;
+prime_table[349]=2357;
+prime_table[350]=2371;
+prime_table[351]=2377;
+prime_table[352]=2381;
+prime_table[353]=2383;
+prime_table[354]=2389;
+prime_table[355]=2393;
+prime_table[356]=2399;
+prime_table[357]=2411;
+prime_table[358]=2417;
+prime_table[359]=2423;
+prime_table[360]=2437;
+prime_table[361]=2441;
+prime_table[362]=2447;
+prime_table[363]=2459;
+prime_table[364]=2467;
+prime_table[365]=2473;
+prime_table[366]=2477;
+prime_table[367]=2503;
+prime_table[368]=2521;
+prime_table[369]=2531;
+prime_table[370]=2539;
+prime_table[371]=2543;
+prime_table[372]=2549;
+prime_table[373]=2551;
+prime_table[374]=2557;
+prime_table[375]=2579;
+prime_table[376]=2591;
+prime_table[377]=2593;
+prime_table[378]=2609;
+prime_table[379]=2617;
+prime_table[380]=2621;
+prime_table[381]=2633;
+prime_table[382]=2647;
+prime_table[383]=2657;
+prime_table[384]=2659;
+prime_table[385]=2663;
+prime_table[386]=2671;
+prime_table[387]=2677;
+prime_table[388]=2683;
+prime_table[389]=2687;
+prime_table[390]=2689;
+prime_table[391]=2693;
+prime_table[392]=2699;
+prime_table[393]=2707;
+prime_table[394]=2711;
+prime_table[395]=2713;
+prime_table[396]=2719;
+prime_table[397]=2729;
+prime_table[398]=2731;
+prime_table[399]=2741;
+prime_table[400]=2749;
+prime_table[401]=2753;
+prime_table[402]=2767;
+prime_table[403]=2777;
+prime_table[404]=2789;
+prime_table[405]=2791;
+prime_table[406]=2797;
+prime_table[407]=2801;
+prime_table[408]=2803;
+prime_table[409]=2819;
+prime_table[410]=2833;
+prime_table[411]=2837;
+prime_table[412]=2843;
+prime_table[413]=2851;
+prime_table[414]=2857;
+prime_table[415]=2861;
+prime_table[416]=2879;
+prime_table[417]=2887;
+prime_table[418]=2897;
+prime_table[419]=2903;
+prime_table[420]=2909;
+prime_table[421]=2917;
+prime_table[422]=2927;
+prime_table[423]=2939;
+prime_table[424]=2953;
+prime_table[425]=2957;
+prime_table[426]=2963;
+prime_table[427]=2969;
+prime_table[428]=2971;
+prime_table[429]=2999;
+prime_table[430]=3001;
+prime_table[431]=3011;
+prime_table[432]=3019;
+prime_table[433]=3023;
+prime_table[434]=3037;
+prime_table[435]=3041;
+prime_table[436]=3049;
+prime_table[437]=3061;
+prime_table[438]=3067;
+prime_table[439]=3079;
+prime_table[440]=3083;
+prime_table[441]=3089;
+prime_table[442]=3109;
+prime_table[443]=3119;
+prime_table[444]=3121;
+prime_table[445]=3137;
+prime_table[446]=3163;
+prime_table[447]=3167;
+prime_table[448]=3169;
+prime_table[449]=3181;
+prime_table[450]=3187;
+prime_table[451]=3191;
+prime_table[452]=3203;
+prime_table[453]=3209;
+prime_table[454]=3217;
+prime_table[455]=3221;
+prime_table[456]=3229;
+prime_table[457]=3251;
+prime_table[458]=3253;
+prime_table[459]=3257;
+prime_table[460]=3259;
+prime_table[461]=3271;
+prime_table[462]=3299;
+prime_table[463]=3301;
+prime_table[464]=3307;
+prime_table[465]=3313;
+prime_table[466]=3319;
+prime_table[467]=3323;
+prime_table[468]=3329;
+prime_table[469]=3331;
+prime_table[470]=3343;
+prime_table[471]=3347;
+prime_table[472]=3359;
+prime_table[473]=3361;
+prime_table[474]=3371;
+prime_table[475]=3373;
+prime_table[476]=3389;
+prime_table[477]=3391;
+prime_table[478]=3407;
+prime_table[479]=3413;
+prime_table[480]=3433;
+prime_table[481]=3449;
+prime_table[482]=3457;
+prime_table[483]=3461;
+prime_table[484]=3463;
+prime_table[485]=3467;
+prime_table[486]=3469;
+prime_table[487]=3491;
+prime_table[488]=3499;
+prime_table[489]=3511;
+prime_table[490]=3517;
+prime_table[491]=3527;
+prime_table[492]=3529;
+prime_table[493]=3533;
+prime_table[494]=3539;
+prime_table[495]=3541;
+prime_table[496]=3547;
+prime_table[497]=3557;
+prime_table[498]=3559;
+prime_table[499]=3571;
+prime_table[500]=3581;
+prime_table[501]=3583;
+prime_table[502]=3593;
+prime_table[503]=3607;
+prime_table[504]=3613;
+prime_table[505]=3617;
+prime_table[506]=3623;
+prime_table[507]=3631;
+prime_table[508]=3637;
+prime_table[509]=3643;
+prime_table[510]=3659;
+prime_table[511]=3671;
+prime_table[512]=3673;
+prime_table[513]=3677;
+prime_table[514]=3691;
+prime_table[515]=3697;
+prime_table[516]=3701;
+prime_table[517]=3709;
+prime_table[518]=3719;
+prime_table[519]=3727;
+prime_table[520]=3733;
+prime_table[521]=3739;
+prime_table[522]=3761;
+prime_table[523]=3767;
+prime_table[524]=3769;
+prime_table[525]=3779;
+prime_table[526]=3793;
+prime_table[527]=3797;
+prime_table[528]=3803;
+prime_table[529]=3821;
+prime_table[530]=3823;
+prime_table[531]=3833;
+prime_table[532]=3847;
+prime_table[533]=3851;
+prime_table[534]=3853;
+prime_table[535]=3863;
+prime_table[536]=3877;
+prime_table[537]=3881;
+prime_table[538]=3889;
+prime_table[539]=3907;
+prime_table[540]=3911;
+prime_table[541]=3917;
+prime_table[542]=3919;
+prime_table[543]=3923;
+prime_table[544]=3929;
+prime_table[545]=3931;
+prime_table[546]=3943;
+prime_table[547]=3947;
+prime_table[548]=3967;
+prime_table[549]=3989;
+prime_table[550]=4001;
+prime_table[551]=4003;
+prime_table[552]=4007;
+prime_table[553]=4013;
+prime_table[554]=4019;
+prime_table[555]=4021;
+prime_table[556]=4027;
+prime_table[557]=4049;
+prime_table[558]=4051;
+prime_table[559]=4057;
+prime_table[560]=4073;
+prime_table[561]=4079;
+prime_table[562]=4091;
+prime_table[563]=4093;
+prime_table[564]=4099;
+prime_table[565]=4111;
+prime_table[566]=4127;
+prime_table[567]=4129;
+prime_table[568]=4133;
+prime_table[569]=4139;
+prime_table[570]=4153;
+prime_table[571]=4157;
+prime_table[572]=4159;
+prime_table[573]=4177;
+prime_table[574]=4201;
+prime_table[575]=4211;
+prime_table[576]=4217;
+prime_table[577]=4219;
+prime_table[578]=4229;
+prime_table[579]=4231;
+prime_table[580]=4241;
+prime_table[581]=4243;
+prime_table[582]=4253;
+prime_table[583]=4259;
+prime_table[584]=4261;
+prime_table[585]=4271;
+prime_table[586]=4273;
+prime_table[587]=4283;
+prime_table[588]=4289;
+prime_table[589]=4297;
+prime_table[590]=4327;
+prime_table[591]=4337;
+prime_table[592]=4339;
+prime_table[593]=4349;
+prime_table[594]=4357;
+prime_table[595]=4363;
+prime_table[596]=4373;
+prime_table[597]=4391;
+prime_table[598]=4397;
+prime_table[599]=4409;
+prime_table[600]=4421;
+prime_table[601]=4423;
+prime_table[602]=4441;
+prime_table[603]=4447;
+prime_table[604]=4451;
+prime_table[605]=4457;
+prime_table[606]=4463;
+prime_table[607]=4481;
+prime_table[608]=4483;
+prime_table[609]=4493;
+prime_table[610]=4507;
+prime_table[611]=4513;
+prime_table[612]=4517;
+prime_table[613]=4519;
+prime_table[614]=4523;
+prime_table[615]=4547;
+prime_table[616]=4549;
+prime_table[617]=4561;
+prime_table[618]=4567;
+prime_table[619]=4583;
+prime_table[620]=4591;
+prime_table[621]=4597;
+prime_table[622]=4603;
+prime_table[623]=4621;
+prime_table[624]=4637;
+prime_table[625]=4639;
+prime_table[626]=4643;
+prime_table[627]=4649;
+prime_table[628]=4651;
+prime_table[629]=4657;
+prime_table[630]=4663;
+prime_table[631]=4673;
+prime_table[632]=4679;
+prime_table[633]=4691;
+prime_table[634]=4703;
+prime_table[635]=4721;
+prime_table[636]=4723;
+prime_table[637]=4729;
+prime_table[638]=4733;
+prime_table[639]=4751;
+prime_table[640]=4759;
+prime_table[641]=4783;
+prime_table[642]=4787;
+prime_table[643]=4789;
+prime_table[644]=4793;
+prime_table[645]=4799;
+prime_table[646]=4801;
+prime_table[647]=4813;
+prime_table[648]=4817;
+prime_table[649]=4831;
+prime_table[650]=4861;
+prime_table[651]=4871;
+prime_table[652]=4877;
+prime_table[653]=4889;
+prime_table[654]=4903;
+prime_table[655]=4909;
+prime_table[656]=4919;
+prime_table[657]=4931;
+prime_table[658]=4933;
+prime_table[659]=4937;
+prime_table[660]=4943;
+prime_table[661]=4951;
+prime_table[662]=4957;
+prime_table[663]=4967;
+prime_table[664]=4969;
+prime_table[665]=4973;
+prime_table[666]=4987;
+prime_table[667]=4993;
+prime_table[668]=4999;
+prime_table[669]=5003;
+prime_table[670]=5009;
+prime_table[671]=5011;
+prime_table[672]=5021;
+prime_table[673]=5023;
+prime_table[674]=5039;
+prime_table[675]=5051;
+prime_table[676]=5059;
+prime_table[677]=5077;
+prime_table[678]=5081;
+prime_table[679]=5087;
+prime_table[680]=5099;
+prime_table[681]=5101;
+prime_table[682]=5107;
+prime_table[683]=5113;
+prime_table[684]=5119;
+prime_table[685]=5147;
+prime_table[686]=5153;
+prime_table[687]=5167;
+prime_table[688]=5171;
+prime_table[689]=5179;
+prime_table[690]=5189;
+prime_table[691]=5197;
+prime_table[692]=5209;
+prime_table[693]=5227;
+prime_table[694]=5231;
+prime_table[695]=5233;
+prime_table[696]=5237;
+prime_table[697]=5261;
+prime_table[698]=5273;
+prime_table[699]=5279;
+prime_table[700]=5281;
+prime_table[701]=5297;
+prime_table[702]=5303;
+prime_table[703]=5309;
+prime_table[704]=5323;
+prime_table[705]=5333;
+prime_table[706]=5347;
+prime_table[707]=5351;
+prime_table[708]=5381;
+prime_table[709]=5387;
+prime_table[710]=5393;
+prime_table[711]=5399;
+prime_table[712]=5407;
+prime_table[713]=5413;
+prime_table[714]=5417;
+prime_table[715]=5419;
+prime_table[716]=5431;
+prime_table[717]=5437;
+prime_table[718]=5441;
+prime_table[719]=5443;
+prime_table[720]=5449;
+prime_table[721]=5471;
+prime_table[722]=5477;
+prime_table[723]=5479;
+prime_table[724]=5483;
+prime_table[725]=5501;
+prime_table[726]=5503;
+prime_table[727]=5507;
+prime_table[728]=5519;
+prime_table[729]=5521;
+prime_table[730]=5527;
+prime_table[731]=5531;
+prime_table[732]=5557;
+prime_table[733]=5563;
+prime_table[734]=5569;
+prime_table[735]=5573;
+prime_table[736]=5581;
+prime_table[737]=5591;
+prime_table[738]=5623;
+prime_table[739]=5639;
+prime_table[740]=5641;
+prime_table[741]=5647;
+prime_table[742]=5651;
+prime_table[743]=5653;
+prime_table[744]=5657;
+prime_table[745]=5659;
+prime_table[746]=5669;
+prime_table[747]=5683;
+prime_table[748]=5689;
+prime_table[749]=5693;
+prime_table[750]=5701;
+prime_table[751]=5711;
+prime_table[752]=5717;
+prime_table[753]=5737;
+prime_table[754]=5741;
+prime_table[755]=5743;
+prime_table[756]=5749;
+prime_table[757]=5779;
+prime_table[758]=5783;
+prime_table[759]=5791;
+prime_table[760]=5801;
+prime_table[761]=5807;
+prime_table[762]=5813;
+prime_table[763]=5821;
+prime_table[764]=5827;
+prime_table[765]=5839;
+prime_table[766]=5843;
+prime_table[767]=5849;
+prime_table[768]=5851;
+prime_table[769]=5857;
+prime_table[770]=5861;
+prime_table[771]=5867;
+prime_table[772]=5869;
+prime_table[773]=5879;
+prime_table[774]=5881;
+prime_table[775]=5897;
+prime_table[776]=5903;
+prime_table[777]=5923;
+prime_table[778]=5927;
+prime_table[779]=5939;
+prime_table[780]=5953;
+prime_table[781]=5981;
+prime_table[782]=5987;
+prime_table[783]=6007;
+prime_table[784]=6011;
+prime_table[785]=6029;
+prime_table[786]=6037;
+prime_table[787]=6043;
+prime_table[788]=6047;
+prime_table[789]=6053;
+prime_table[790]=6067;
+prime_table[791]=6073;
+prime_table[792]=6079;
+prime_table[793]=6089;
+prime_table[794]=6091;
+prime_table[795]=6101;
+prime_table[796]=6113;
+prime_table[797]=6121;
+prime_table[798]=6131;
+prime_table[799]=6133;
+prime_table[800]=6143;
+prime_table[801]=6151;
+prime_table[802]=6163;
+prime_table[803]=6173;
+prime_table[804]=6197;
+prime_table[805]=6199;
+prime_table[806]=6203;
+prime_table[807]=6211;
+prime_table[808]=6217;
+prime_table[809]=6221;
+prime_table[810]=6229;
+prime_table[811]=6247;
+prime_table[812]=6257;
+prime_table[813]=6263;
+prime_table[814]=6269;
+prime_table[815]=6271;
+prime_table[816]=6277;
+prime_table[817]=6287;
+prime_table[818]=6299;
+prime_table[819]=6301;
+prime_table[820]=6311;
+prime_table[821]=6317;
+prime_table[822]=6323;
+prime_table[823]=6329;
+prime_table[824]=6337;
+prime_table[825]=6343;
+prime_table[826]=6353;
+prime_table[827]=6359;
+prime_table[828]=6361;
+prime_table[829]=6367;
+prime_table[830]=6373;
+prime_table[831]=6379;
+prime_table[832]=6389;
+prime_table[833]=6397;
+prime_table[834]=6421;
+prime_table[835]=6427;
+prime_table[836]=6449;
+prime_table[837]=6451;
+prime_table[838]=6469;
+prime_table[839]=6473;
+prime_table[840]=6481;
+prime_table[841]=6491;
+prime_table[842]=6521;
+prime_table[843]=6529;
+prime_table[844]=6547;
+prime_table[845]=6551;
+prime_table[846]=6553;
+prime_table[847]=6563;
+prime_table[848]=6569;
+prime_table[849]=6571;
+prime_table[850]=6577;
+prime_table[851]=6581;
+prime_table[852]=6599;
+prime_table[853]=6607;
+prime_table[854]=6619;
+prime_table[855]=6637;
+prime_table[856]=6653;
+prime_table[857]=6659;
+prime_table[858]=6661;
+prime_table[859]=6673;
+prime_table[860]=6679;
+prime_table[861]=6689;
+prime_table[862]=6691;
+prime_table[863]=6701;
+prime_table[864]=6703;
+prime_table[865]=6709;
+prime_table[866]=6719;
+prime_table[867]=6733;
+prime_table[868]=6737;
+prime_table[869]=6761;
+prime_table[870]=6763;
+prime_table[871]=6779;
+prime_table[872]=6781;
+prime_table[873]=6791;
+prime_table[874]=6793;
+prime_table[875]=6803;
+prime_table[876]=6823;
+prime_table[877]=6827;
+prime_table[878]=6829;
+prime_table[879]=6833;
+prime_table[880]=6841;
+prime_table[881]=6857;
+prime_table[882]=6863;
+prime_table[883]=6869;
+prime_table[884]=6871;
+prime_table[885]=6883;
+prime_table[886]=6899;
+prime_table[887]=6907;
+prime_table[888]=6911;
+prime_table[889]=6917;
+prime_table[890]=6947;
+prime_table[891]=6949;
+prime_table[892]=6959;
+prime_table[893]=6961;
+prime_table[894]=6967;
+prime_table[895]=6971;
+prime_table[896]=6977;
+prime_table[897]=6983;
+prime_table[898]=6991;
+prime_table[899]=6997;
+prime_table[900]=7001;
+prime_table[901]=7013;
+prime_table[902]=7019;
+prime_table[903]=7027;
+prime_table[904]=7039;
+prime_table[905]=7043;
+prime_table[906]=7057;
+prime_table[907]=7069;
+prime_table[908]=7079;
+prime_table[909]=7103;
+prime_table[910]=7109;
+prime_table[911]=7121;
+prime_table[912]=7127;
+prime_table[913]=7129;
+prime_table[914]=7151;
+prime_table[915]=7159;
+prime_table[916]=7177;
+prime_table[917]=7187;
+prime_table[918]=7193;
+prime_table[919]=7207;
+prime_table[920]=7211;
+prime_table[921]=7213;
+prime_table[922]=7219;
+prime_table[923]=7229;
+prime_table[924]=7237;
+prime_table[925]=7243;
+prime_table[926]=7247;
+prime_table[927]=7253;
+prime_table[928]=7283;
+prime_table[929]=7297;
+prime_table[930]=7307;
+prime_table[931]=7309;
+prime_table[932]=7321;
+prime_table[933]=7331;
+prime_table[934]=7333;
+prime_table[935]=7349;
+prime_table[936]=7351;
+prime_table[937]=7369;
+prime_table[938]=7393;
+prime_table[939]=7411;
+prime_table[940]=7417;
+prime_table[941]=7433;
+prime_table[942]=7451;
+prime_table[943]=7457;
+prime_table[944]=7459;
+prime_table[945]=7477;
+prime_table[946]=7481;
+prime_table[947]=7487;
+prime_table[948]=7489;
+prime_table[949]=7499;
+prime_table[950]=7507;
+prime_table[951]=7517;
+prime_table[952]=7523;
+prime_table[953]=7529;
+prime_table[954]=7537;
+prime_table[955]=7541;
+prime_table[956]=7547;
+prime_table[957]=7549;
+prime_table[958]=7559;
+prime_table[959]=7561;
+prime_table[960]=7573;
+prime_table[961]=7577;
+prime_table[962]=7583;
+prime_table[963]=7589;
+prime_table[964]=7591;
+prime_table[965]=7603;
+prime_table[966]=7607;
+prime_table[967]=7621;
+prime_table[968]=7639;
+prime_table[969]=7643;
+prime_table[970]=7649;
+prime_table[971]=7669;
+prime_table[972]=7673;
+prime_table[973]=7681;
+prime_table[974]=7687;
+prime_table[975]=7691;
+prime_table[976]=7699;
+prime_table[977]=7703;
+prime_table[978]=7717;
+prime_table[979]=7723;
+prime_table[980]=7727;
+prime_table[981]=7741;
+prime_table[982]=7753;
+prime_table[983]=7757;
+prime_table[984]=7759;
+prime_table[985]=7789;
+prime_table[986]=7793;
+prime_table[987]=7817;
+prime_table[988]=7823;
+prime_table[989]=7829;
+prime_table[990]=7841;
+prime_table[991]=7853;
+prime_table[992]=7867;
+prime_table[993]=7873;
+prime_table[994]=7877;
+prime_table[995]=7879;
+prime_table[996]=7883;
+prime_table[997]=7901;
+prime_table[998]=7907;
+prime_table[999]=7919;
+prime_table[1000]=7927;
+prime_table[1001]=7933;
+prime_table[1002]=7937;
+prime_table[1003]=7949;
+prime_table[1004]=7951;
+prime_table[1005]=7963;
+prime_table[1006]=7993;
+prime_table[1007]=8009;
+prime_table[1008]=8011;
+prime_table[1009]=8017;
+prime_table[1010]=8039;
+prime_table[1011]=8053;
+prime_table[1012]=8059;
+prime_table[1013]=8069;
+prime_table[1014]=8081;
+prime_table[1015]=8087;
+prime_table[1016]=8089;
+prime_table[1017]=8093;
+prime_table[1018]=8101;
+prime_table[1019]=8111;
+prime_table[1020]=8117;
+prime_table[1021]=8123;
+prime_table[1022]=8147;
+prime_table[1023]=8161;
+prime_table[1024]=8167;
+prime_table[1025]=8171;
+prime_table[1026]=8179;
+prime_table[1027]=8191;
+prime_table[1028]=8209;
+prime_table[1029]=8219;
+prime_table[1030]=8221;
+prime_table[1031]=8231;
+prime_table[1032]=8233;
+prime_table[1033]=8237;
+prime_table[1034]=8243;
+prime_table[1035]=8263;
+prime_table[1036]=8269;
+prime_table[1037]=8273;
+prime_table[1038]=8287;
+prime_table[1039]=8291;
+prime_table[1040]=8293;
+prime_table[1041]=8297;
+prime_table[1042]=8311;
+prime_table[1043]=8317;
+prime_table[1044]=8329;
+prime_table[1045]=8353;
+prime_table[1046]=8363;
+prime_table[1047]=8369;
+prime_table[1048]=8377;
+prime_table[1049]=8387;
+prime_table[1050]=8389;
+prime_table[1051]=8419;
+prime_table[1052]=8423;
+prime_table[1053]=8429;
+prime_table[1054]=8431;
+prime_table[1055]=8443;
+prime_table[1056]=8447;
+prime_table[1057]=8461;
+prime_table[1058]=8467;
+prime_table[1059]=8501;
+prime_table[1060]=8513;
+prime_table[1061]=8521;
+prime_table[1062]=8527;
+prime_table[1063]=8537;
+prime_table[1064]=8539;
+prime_table[1065]=8543;
+prime_table[1066]=8563;
+prime_table[1067]=8573;
+prime_table[1068]=8581;
+prime_table[1069]=8597;
+prime_table[1070]=8599;
+prime_table[1071]=8609;
+prime_table[1072]=8623;
+prime_table[1073]=8627;
+prime_table[1074]=8629;
+prime_table[1075]=8641;
+prime_table[1076]=8647;
+prime_table[1077]=8663;
+prime_table[1078]=8669;
+prime_table[1079]=8677;
+prime_table[1080]=8681;
+prime_table[1081]=8689;
+prime_table[1082]=8693;
+prime_table[1083]=8699;
+prime_table[1084]=8707;
+prime_table[1085]=8713;
+prime_table[1086]=8719;
+prime_table[1087]=8731;
+prime_table[1088]=8737;
+prime_table[1089]=8741;
+prime_table[1090]=8747;
+prime_table[1091]=8753;
+prime_table[1092]=8761;
+prime_table[1093]=8779;
+prime_table[1094]=8783;
+prime_table[1095]=8803;
+prime_table[1096]=8807;
+prime_table[1097]=8819;
+prime_table[1098]=8821;
+prime_table[1099]=8831;
+prime_table[1100]=8837;
+prime_table[1101]=8839;
+prime_table[1102]=8849;
+prime_table[1103]=8861;
+prime_table[1104]=8863;
+prime_table[1105]=8867;
+prime_table[1106]=8887;
+prime_table[1107]=8893;
+prime_table[1108]=8923;
+prime_table[1109]=8929;
+prime_table[1110]=8933;
+prime_table[1111]=8941;
+prime_table[1112]=8951;
+prime_table[1113]=8963;
+prime_table[1114]=8969;
+prime_table[1115]=8971;
+prime_table[1116]=8999;
+prime_table[1117]=9001;
+prime_table[1118]=9007;
+prime_table[1119]=9011;
+prime_table[1120]=9013;
+prime_table[1121]=9029;
+prime_table[1122]=9041;
+prime_table[1123]=9043;
+prime_table[1124]=9049;
+prime_table[1125]=9059;
+prime_table[1126]=9067;
+prime_table[1127]=9091;
+prime_table[1128]=9103;
+prime_table[1129]=9109;
+prime_table[1130]=9127;
+prime_table[1131]=9133;
+prime_table[1132]=9137;
+prime_table[1133]=9151;
+prime_table[1134]=9157;
+prime_table[1135]=9161;
+prime_table[1136]=9173;
+prime_table[1137]=9181;
+prime_table[1138]=9187;
+prime_table[1139]=9199;
+prime_table[1140]=9203;
+prime_table[1141]=9209;
+prime_table[1142]=9221;
+prime_table[1143]=9227;
+prime_table[1144]=9239;
+prime_table[1145]=9241;
+prime_table[1146]=9257;
+prime_table[1147]=9277;
+prime_table[1148]=9281;
+prime_table[1149]=9283;
+prime_table[1150]=9293;
+prime_table[1151]=9311;
+prime_table[1152]=9319;
+prime_table[1153]=9323;
+prime_table[1154]=9337;
+prime_table[1155]=9341;
+prime_table[1156]=9343;
+prime_table[1157]=9349;
+prime_table[1158]=9371;
+prime_table[1159]=9377;
+prime_table[1160]=9391;
+prime_table[1161]=9397;
+prime_table[1162]=9403;
+prime_table[1163]=9413;
+prime_table[1164]=9419;
+prime_table[1165]=9421;
+prime_table[1166]=9431;
+prime_table[1167]=9433;
+prime_table[1168]=9437;
+prime_table[1169]=9439;
+prime_table[1170]=9461;
+prime_table[1171]=9463;
+prime_table[1172]=9467;
+prime_table[1173]=9473;
+prime_table[1174]=9479;
+prime_table[1175]=9491;
+prime_table[1176]=9497;
+prime_table[1177]=9511;
+prime_table[1178]=9521;
+prime_table[1179]=9533;
+prime_table[1180]=9539;
+prime_table[1181]=9547;
+prime_table[1182]=9551;
+prime_table[1183]=9587;
+prime_table[1184]=9601;
+prime_table[1185]=9613;
+prime_table[1186]=9619;
+prime_table[1187]=9623;
+prime_table[1188]=9629;
+prime_table[1189]=9631;
+prime_table[1190]=9643;
+prime_table[1191]=9649;
+prime_table[1192]=9661;
+prime_table[1193]=9677;
+prime_table[1194]=9679;
+prime_table[1195]=9689;
+prime_table[1196]=9697;
+prime_table[1197]=9719;
+prime_table[1198]=9721;
+prime_table[1199]=9733;
+prime_table[1200]=9739;
+prime_table[1201]=9743;
+prime_table[1202]=9749;
+prime_table[1203]=9767;
+prime_table[1204]=9769;
+prime_table[1205]=9781;
+prime_table[1206]=9787;
+prime_table[1207]=9791;
+prime_table[1208]=9803;
+prime_table[1209]=9811;
+prime_table[1210]=9817;
+prime_table[1211]=9829;
+prime_table[1212]=9833;
+prime_table[1213]=9839;
+prime_table[1214]=9851;
+prime_table[1215]=9857;
+prime_table[1216]=9859;
+prime_table[1217]=9871;
+prime_table[1218]=9883;
+prime_table[1219]=9887;
+prime_table[1220]=9901;
+prime_table[1221]=9907;
+prime_table[1222]=9923;
+prime_table[1223]=9929;
+prime_table[1224]=9931;
+prime_table[1225]=9941;
+prime_table[1226]=9949;
+prime_table[1227]=9967;
+prime_table[1228]=9973;
+prime_table[1229]=10007;
+prime_table[1230]=10009;
+prime_table[1231]=10037;
+prime_table[1232]=10039;
+prime_table[1233]=10061;
+prime_table[1234]=10067;
+prime_table[1235]=10069;
+prime_table[1236]=10079;
+prime_table[1237]=10091;
+prime_table[1238]=10093;
+prime_table[1239]=10099;
+prime_table[1240]=10103;
+prime_table[1241]=10111;
+prime_table[1242]=10133;
+prime_table[1243]=10139;
+prime_table[1244]=10141;
+prime_table[1245]=10151;
+prime_table[1246]=10159;
+prime_table[1247]=10163;
+prime_table[1248]=10169;
+prime_table[1249]=10177;
+prime_table[1250]=10181;
+prime_table[1251]=10193;
+prime_table[1252]=10211;
+prime_table[1253]=10223;
+prime_table[1254]=10243;
+prime_table[1255]=10247;
+prime_table[1256]=10253;
+prime_table[1257]=10259;
+prime_table[1258]=10267;
+prime_table[1259]=10271;
+prime_table[1260]=10273;
+prime_table[1261]=10289;
+prime_table[1262]=10301;
+prime_table[1263]=10303;
+prime_table[1264]=10313;
+prime_table[1265]=10321;
+prime_table[1266]=10331;
+prime_table[1267]=10333;
+prime_table[1268]=10337;
+prime_table[1269]=10343;
+prime_table[1270]=10357;
+prime_table[1271]=10369;
+prime_table[1272]=10391;
+prime_table[1273]=10399;
+prime_table[1274]=10427;
+prime_table[1275]=10429;
+prime_table[1276]=10433;
+prime_table[1277]=10453;
+prime_table[1278]=10457;
+prime_table[1279]=10459;
+prime_table[1280]=10463;
+prime_table[1281]=10477;
+prime_table[1282]=10487;
+prime_table[1283]=10499;
+prime_table[1284]=10501;
+prime_table[1285]=10513;
+prime_table[1286]=10529;
+prime_table[1287]=10531;
+prime_table[1288]=10559;
+prime_table[1289]=10567;
+prime_table[1290]=10589;
+prime_table[1291]=10597;
+prime_table[1292]=10601;
+prime_table[1293]=10607;
+prime_table[1294]=10613;
+prime_table[1295]=10627;
+prime_table[1296]=10631;
+prime_table[1297]=10639;
+prime_table[1298]=10651;
+prime_table[1299]=10657;
+prime_table[1300]=10663;
+prime_table[1301]=10667;
+prime_table[1302]=10687;
+prime_table[1303]=10691;
+prime_table[1304]=10709;
+prime_table[1305]=10711;
+prime_table[1306]=10723;
+prime_table[1307]=10729;
+prime_table[1308]=10733;
+prime_table[1309]=10739;
+prime_table[1310]=10753;
+prime_table[1311]=10771;
+prime_table[1312]=10781;
+prime_table[1313]=10789;
+prime_table[1314]=10799;
+prime_table[1315]=10831;
+prime_table[1316]=10837;
+prime_table[1317]=10847;
+prime_table[1318]=10853;
+prime_table[1319]=10859;
+prime_table[1320]=10861;
+prime_table[1321]=10867;
+prime_table[1322]=10883;
+prime_table[1323]=10889;
+prime_table[1324]=10891;
+prime_table[1325]=10903;
+prime_table[1326]=10909;
+prime_table[1327]=10937;
+prime_table[1328]=10939;
+prime_table[1329]=10949;
+prime_table[1330]=10957;
+prime_table[1331]=10973;
+prime_table[1332]=10979;
+prime_table[1333]=10987;
+prime_table[1334]=10993;
+prime_table[1335]=11003;
+prime_table[1336]=11027;
+prime_table[1337]=11047;
+prime_table[1338]=11057;
+prime_table[1339]=11059;
+prime_table[1340]=11069;
+prime_table[1341]=11071;
+prime_table[1342]=11083;
+prime_table[1343]=11087;
+prime_table[1344]=11093;
+prime_table[1345]=11113;
+prime_table[1346]=11117;
+prime_table[1347]=11119;
+prime_table[1348]=11131;
+prime_table[1349]=11149;
+prime_table[1350]=11159;
+prime_table[1351]=11161;
+prime_table[1352]=11171;
+prime_table[1353]=11173;
+prime_table[1354]=11177;
+prime_table[1355]=11197;
+prime_table[1356]=11213;
+prime_table[1357]=11239;
+prime_table[1358]=11243;
+prime_table[1359]=11251;
+prime_table[1360]=11257;
+prime_table[1361]=11261;
+prime_table[1362]=11273;
+prime_table[1363]=11279;
+prime_table[1364]=11287;
+prime_table[1365]=11299;
+prime_table[1366]=11311;
+prime_table[1367]=11317;
+prime_table[1368]=11321;
+prime_table[1369]=11329;
+prime_table[1370]=11351;
+prime_table[1371]=11353;
+prime_table[1372]=11369;
+prime_table[1373]=11383;
+prime_table[1374]=11393;
+prime_table[1375]=11399;
+prime_table[1376]=11411;
+prime_table[1377]=11423;
+prime_table[1378]=11437;
+prime_table[1379]=11443;
+prime_table[1380]=11447;
+prime_table[1381]=11467;
+prime_table[1382]=11471;
+prime_table[1383]=11483;
+prime_table[1384]=11489;
+prime_table[1385]=11491;
+prime_table[1386]=11497;
+prime_table[1387]=11503;
+prime_table[1388]=11519;
+prime_table[1389]=11527;
+prime_table[1390]=11549;
+prime_table[1391]=11551;
+prime_table[1392]=11579;
+prime_table[1393]=11587;
+prime_table[1394]=11593;
+prime_table[1395]=11597;
+prime_table[1396]=11617;
+prime_table[1397]=11621;
+prime_table[1398]=11633;
+prime_table[1399]=11657;
+prime_table[1400]=11677;
+prime_table[1401]=11681;
+prime_table[1402]=11689;
+prime_table[1403]=11699;
+prime_table[1404]=11701;
+prime_table[1405]=11717;
+prime_table[1406]=11719;
+prime_table[1407]=11731;
+prime_table[1408]=11743;
+prime_table[1409]=11777;
+prime_table[1410]=11779;
+prime_table[1411]=11783;
+prime_table[1412]=11789;
+prime_table[1413]=11801;
+prime_table[1414]=11807;
+prime_table[1415]=11813;
+prime_table[1416]=11821;
+prime_table[1417]=11827;
+prime_table[1418]=11831;
+prime_table[1419]=11833;
+prime_table[1420]=11839;
+prime_table[1421]=11863;
+prime_table[1422]=11867;
+prime_table[1423]=11887;
+prime_table[1424]=11897;
+prime_table[1425]=11903;
+prime_table[1426]=11909;
+prime_table[1427]=11923;
+prime_table[1428]=11927;
+prime_table[1429]=11933;
+prime_table[1430]=11939;
+prime_table[1431]=11941;
+prime_table[1432]=11953;
+prime_table[1433]=11959;
+prime_table[1434]=11969;
+prime_table[1435]=11971;
+prime_table[1436]=11981;
+prime_table[1437]=11987;
+prime_table[1438]=12007;
+prime_table[1439]=12011;
+prime_table[1440]=12037;
+prime_table[1441]=12041;
+prime_table[1442]=12043;
+prime_table[1443]=12049;
+prime_table[1444]=12071;
+prime_table[1445]=12073;
+prime_table[1446]=12097;
+prime_table[1447]=12101;
+prime_table[1448]=12107;
+prime_table[1449]=12109;
+prime_table[1450]=12113;
+prime_table[1451]=12119;
+prime_table[1452]=12143;
+prime_table[1453]=12149;
+prime_table[1454]=12157;
+prime_table[1455]=12161;
+prime_table[1456]=12163;
+prime_table[1457]=12197;
+prime_table[1458]=12203;
+prime_table[1459]=12211;
+prime_table[1460]=12227;
+prime_table[1461]=12239;
+prime_table[1462]=12241;
+prime_table[1463]=12251;
+prime_table[1464]=12253;
+prime_table[1465]=12263;
+prime_table[1466]=12269;
+prime_table[1467]=12277;
+prime_table[1468]=12281;
+prime_table[1469]=12289;
+prime_table[1470]=12301;
+prime_table[1471]=12323;
+prime_table[1472]=12329;
+prime_table[1473]=12343;
+prime_table[1474]=12347;
+prime_table[1475]=12373;
+prime_table[1476]=12377;
+prime_table[1477]=12379;
+prime_table[1478]=12391;
+prime_table[1479]=12401;
+prime_table[1480]=12409;
+prime_table[1481]=12413;
+prime_table[1482]=12421;
+prime_table[1483]=12433;
+prime_table[1484]=12437;
+prime_table[1485]=12451;
+prime_table[1486]=12457;
+prime_table[1487]=12473;
+prime_table[1488]=12479;
+prime_table[1489]=12487;
+prime_table[1490]=12491;
+prime_table[1491]=12497;
+prime_table[1492]=12503;
+prime_table[1493]=12511;
+prime_table[1494]=12517;
+prime_table[1495]=12527;
+prime_table[1496]=12539;
+prime_table[1497]=12541;
+prime_table[1498]=12547;
+prime_table[1499]=12553;
+prime_table[1500]=12569;
+prime_table[1501]=12577;
+prime_table[1502]=12583;
+prime_table[1503]=12589;
+prime_table[1504]=12601;
+prime_table[1505]=12611;
+prime_table[1506]=12613;
+prime_table[1507]=12619;
+prime_table[1508]=12637;
+prime_table[1509]=12641;
+prime_table[1510]=12647;
+prime_table[1511]=12653;
+prime_table[1512]=12659;
+prime_table[1513]=12671;
+prime_table[1514]=12689;
+prime_table[1515]=12697;
+prime_table[1516]=12703;
+prime_table[1517]=12713;
+prime_table[1518]=12721;
+prime_table[1519]=12739;
+prime_table[1520]=12743;
+prime_table[1521]=12757;
+prime_table[1522]=12763;
+prime_table[1523]=12781;
+prime_table[1524]=12791;
+prime_table[1525]=12799;
+prime_table[1526]=12809;
+prime_table[1527]=12821;
+prime_table[1528]=12823;
+prime_table[1529]=12829;
+prime_table[1530]=12841;
+prime_table[1531]=12853;
+prime_table[1532]=12889;
+prime_table[1533]=12893;
+prime_table[1534]=12899;
+prime_table[1535]=12907;
+prime_table[1536]=12911;
+prime_table[1537]=12917;
+prime_table[1538]=12919;
+prime_table[1539]=12923;
+prime_table[1540]=12941;
+prime_table[1541]=12953;
+prime_table[1542]=12959;
+prime_table[1543]=12967;
+prime_table[1544]=12973;
+prime_table[1545]=12979;
+prime_table[1546]=12983;
+prime_table[1547]=13001;
+prime_table[1548]=13003;
+prime_table[1549]=13007;
+prime_table[1550]=13009;
+prime_table[1551]=13033;
+prime_table[1552]=13037;
+prime_table[1553]=13043;
+prime_table[1554]=13049;
+prime_table[1555]=13063;
+prime_table[1556]=13093;
+prime_table[1557]=13099;
+prime_table[1558]=13103;
+prime_table[1559]=13109;
+prime_table[1560]=13121;
+prime_table[1561]=13127;
+prime_table[1562]=13147;
+prime_table[1563]=13151;
+prime_table[1564]=13159;
+prime_table[1565]=13163;
+prime_table[1566]=13171;
+prime_table[1567]=13177;
+prime_table[1568]=13183;
+prime_table[1569]=13187;
+prime_table[1570]=13217;
+prime_table[1571]=13219;
+prime_table[1572]=13229;
+prime_table[1573]=13241;
+prime_table[1574]=13249;
+prime_table[1575]=13259;
+prime_table[1576]=13267;
+prime_table[1577]=13291;
+prime_table[1578]=13297;
+prime_table[1579]=13309;
+prime_table[1580]=13313;
+prime_table[1581]=13327;
+prime_table[1582]=13331;
+prime_table[1583]=13337;
+prime_table[1584]=13339;
+prime_table[1585]=13367;
+prime_table[1586]=13381;
+prime_table[1587]=13397;
+prime_table[1588]=13399;
+prime_table[1589]=13411;
+prime_table[1590]=13417;
+prime_table[1591]=13421;
+prime_table[1592]=13441;
+prime_table[1593]=13451;
+prime_table[1594]=13457;
+prime_table[1595]=13463;
+prime_table[1596]=13469;
+prime_table[1597]=13477;
+prime_table[1598]=13487;
+prime_table[1599]=13499;
+prime_table[1600]=13513;
+prime_table[1601]=13523;
+prime_table[1602]=13537;
+prime_table[1603]=13553;
+prime_table[1604]=13567;
+prime_table[1605]=13577;
+prime_table[1606]=13591;
+prime_table[1607]=13597;
+prime_table[1608]=13613;
+prime_table[1609]=13619;
+prime_table[1610]=13627;
+prime_table[1611]=13633;
+prime_table[1612]=13649;
+prime_table[1613]=13669;
+prime_table[1614]=13679;
+prime_table[1615]=13681;
+prime_table[1616]=13687;
+prime_table[1617]=13691;
+prime_table[1618]=13693;
+prime_table[1619]=13697;
+prime_table[1620]=13709;
+prime_table[1621]=13711;
+prime_table[1622]=13721;
+prime_table[1623]=13723;
+prime_table[1624]=13729;
+prime_table[1625]=13751;
+prime_table[1626]=13757;
+prime_table[1627]=13759;
+prime_table[1628]=13763;
+prime_table[1629]=13781;
+prime_table[1630]=13789;
+prime_table[1631]=13799;
+prime_table[1632]=13807;
+prime_table[1633]=13829;
+prime_table[1634]=13831;
+prime_table[1635]=13841;
+prime_table[1636]=13859;
+prime_table[1637]=13873;
+prime_table[1638]=13877;
+prime_table[1639]=13879;
+prime_table[1640]=13883;
+prime_table[1641]=13901;
+prime_table[1642]=13903;
+prime_table[1643]=13907;
+prime_table[1644]=13913;
+prime_table[1645]=13921;
+prime_table[1646]=13931;
+prime_table[1647]=13933;
+prime_table[1648]=13963;
+prime_table[1649]=13967;
+prime_table[1650]=13997;
+prime_table[1651]=13999;
+prime_table[1652]=14009;
+prime_table[1653]=14011;
+prime_table[1654]=14029;
+prime_table[1655]=14033;
+prime_table[1656]=14051;
+prime_table[1657]=14057;
+prime_table[1658]=14071;
+prime_table[1659]=14081;
+prime_table[1660]=14083;
+prime_table[1661]=14087;
+prime_table[1662]=14107;
+prime_table[1663]=14143;
+prime_table[1664]=14149;
+prime_table[1665]=14153;
+prime_table[1666]=14159;
+prime_table[1667]=14173;
+prime_table[1668]=14177;
+prime_table[1669]=14197;
+prime_table[1670]=14207;
+prime_table[1671]=14221;
+prime_table[1672]=14243;
+prime_table[1673]=14249;
+prime_table[1674]=14251;
+prime_table[1675]=14281;
+prime_table[1676]=14293;
+prime_table[1677]=14303;
+prime_table[1678]=14321;
+prime_table[1679]=14323;
+prime_table[1680]=14327;
+prime_table[1681]=14341;
+prime_table[1682]=14347;
+prime_table[1683]=14369;
+prime_table[1684]=14387;
+prime_table[1685]=14389;
+prime_table[1686]=14401;
+prime_table[1687]=14407;
+prime_table[1688]=14411;
+prime_table[1689]=14419;
+prime_table[1690]=14423;
+prime_table[1691]=14431;
+prime_table[1692]=14437;
+prime_table[1693]=14447;
+prime_table[1694]=14449;
+prime_table[1695]=14461;
+prime_table[1696]=14479;
+prime_table[1697]=14489;
+prime_table[1698]=14503;
+prime_table[1699]=14519;
+prime_table[1700]=14533;
+prime_table[1701]=14537;
+prime_table[1702]=14543;
+prime_table[1703]=14549;
+prime_table[1704]=14551;
+prime_table[1705]=14557;
+prime_table[1706]=14561;
+prime_table[1707]=14563;
+prime_table[1708]=14591;
+prime_table[1709]=14593;
+prime_table[1710]=14621;
+prime_table[1711]=14627;
+prime_table[1712]=14629;
+prime_table[1713]=14633;
+prime_table[1714]=14639;
+prime_table[1715]=14653;
+prime_table[1716]=14657;
+prime_table[1717]=14669;
+prime_table[1718]=14683;
+prime_table[1719]=14699;
+prime_table[1720]=14713;
+prime_table[1721]=14717;
+prime_table[1722]=14723;
+prime_table[1723]=14731;
+prime_table[1724]=14737;
+prime_table[1725]=14741;
+prime_table[1726]=14747;
+prime_table[1727]=14753;
+prime_table[1728]=14759;
+prime_table[1729]=14767;
+prime_table[1730]=14771;
+prime_table[1731]=14779;
+prime_table[1732]=14783;
+prime_table[1733]=14797;
+prime_table[1734]=14813;
+prime_table[1735]=14821;
+prime_table[1736]=14827;
+prime_table[1737]=14831;
+prime_table[1738]=14843;
+prime_table[1739]=14851;
+prime_table[1740]=14867;
+prime_table[1741]=14869;
+prime_table[1742]=14879;
+prime_table[1743]=14887;
+prime_table[1744]=14891;
+prime_table[1745]=14897;
+prime_table[1746]=14923;
+prime_table[1747]=14929;
+prime_table[1748]=14939;
+prime_table[1749]=14947;
+prime_table[1750]=14951;
+prime_table[1751]=14957;
+prime_table[1752]=14969;
+prime_table[1753]=14983;
+prime_table[1754]=15013;
+prime_table[1755]=15017;
+prime_table[1756]=15031;
+prime_table[1757]=15053;
+prime_table[1758]=15061;
+prime_table[1759]=15073;
+prime_table[1760]=15077;
+prime_table[1761]=15083;
+prime_table[1762]=15091;
+prime_table[1763]=15101;
+prime_table[1764]=15107;
+prime_table[1765]=15121;
+prime_table[1766]=15131;
+prime_table[1767]=15137;
+prime_table[1768]=15139;
+prime_table[1769]=15149;
+prime_table[1770]=15161;
+prime_table[1771]=15173;
+prime_table[1772]=15187;
+prime_table[1773]=15193;
+prime_table[1774]=15199;
+prime_table[1775]=15217;
+prime_table[1776]=15227;
+prime_table[1777]=15233;
+prime_table[1778]=15241;
+prime_table[1779]=15259;
+prime_table[1780]=15263;
+prime_table[1781]=15269;
+prime_table[1782]=15271;
+prime_table[1783]=15277;
+prime_table[1784]=15287;
+prime_table[1785]=15289;
+prime_table[1786]=15299;
+prime_table[1787]=15307;
+prime_table[1788]=15313;
+prime_table[1789]=15319;
+prime_table[1790]=15329;
+prime_table[1791]=15331;
+prime_table[1792]=15349;
+prime_table[1793]=15359;
+prime_table[1794]=15361;
+prime_table[1795]=15373;
+prime_table[1796]=15377;
+prime_table[1797]=15383;
+prime_table[1798]=15391;
+prime_table[1799]=15401;
+prime_table[1800]=15413;
+prime_table[1801]=15427;
+prime_table[1802]=15439;
+prime_table[1803]=15443;
+prime_table[1804]=15451;
+prime_table[1805]=15461;
+prime_table[1806]=15467;
+prime_table[1807]=15473;
+prime_table[1808]=15493;
+prime_table[1809]=15497;
+prime_table[1810]=15511;
+prime_table[1811]=15527;
+prime_table[1812]=15541;
+prime_table[1813]=15551;
+prime_table[1814]=15559;
+prime_table[1815]=15569;
+prime_table[1816]=15581;
+prime_table[1817]=15583;
+prime_table[1818]=15601;
+prime_table[1819]=15607;
+prime_table[1820]=15619;
+prime_table[1821]=15629;
+prime_table[1822]=15641;
+prime_table[1823]=15643;
+prime_table[1824]=15647;
+prime_table[1825]=15649;
+prime_table[1826]=15661;
+prime_table[1827]=15667;
+prime_table[1828]=15671;
+prime_table[1829]=15679;
+prime_table[1830]=15683;
+prime_table[1831]=15727;
+prime_table[1832]=15731;
+prime_table[1833]=15733;
+prime_table[1834]=15737;
+prime_table[1835]=15739;
+prime_table[1836]=15749;
+prime_table[1837]=15761;
+prime_table[1838]=15767;
+prime_table[1839]=15773;
+prime_table[1840]=15787;
+prime_table[1841]=15791;
+prime_table[1842]=15797;
+prime_table[1843]=15803;
+prime_table[1844]=15809;
+prime_table[1845]=15817;
+prime_table[1846]=15823;
+prime_table[1847]=15859;
+prime_table[1848]=15877;
+prime_table[1849]=15881;
+prime_table[1850]=15887;
+prime_table[1851]=15889;
+prime_table[1852]=15901;
+prime_table[1853]=15907;
+prime_table[1854]=15913;
+prime_table[1855]=15919;
+prime_table[1856]=15923;
+prime_table[1857]=15937;
+prime_table[1858]=15959;
+prime_table[1859]=15971;
+prime_table[1860]=15973;
+prime_table[1861]=15991;
+prime_table[1862]=16001;
+prime_table[1863]=16007;
+prime_table[1864]=16033;
+prime_table[1865]=16057;
+prime_table[1866]=16061;
+prime_table[1867]=16063;
+prime_table[1868]=16067;
+prime_table[1869]=16069;
+prime_table[1870]=16073;
+prime_table[1871]=16087;
+prime_table[1872]=16091;
+prime_table[1873]=16097;
+prime_table[1874]=16103;
+prime_table[1875]=16111;
+prime_table[1876]=16127;
+prime_table[1877]=16139;
+prime_table[1878]=16141;
+prime_table[1879]=16183;
+prime_table[1880]=16187;
+prime_table[1881]=16189;
+prime_table[1882]=16193;
+prime_table[1883]=16217;
+prime_table[1884]=16223;
+prime_table[1885]=16229;
+prime_table[1886]=16231;
+prime_table[1887]=16249;
+prime_table[1888]=16253;
+prime_table[1889]=16267;
+prime_table[1890]=16273;
+prime_table[1891]=16301;
+prime_table[1892]=16319;
+prime_table[1893]=16333;
+prime_table[1894]=16339;
+prime_table[1895]=16349;
+prime_table[1896]=16361;
+prime_table[1897]=16363;
+prime_table[1898]=16369;
+prime_table[1899]=16381;
+prime_table[1900]=16411;
+prime_table[1901]=16417;
+prime_table[1902]=16421;
+prime_table[1903]=16427;
+prime_table[1904]=16433;
+prime_table[1905]=16447;
+prime_table[1906]=16451;
+prime_table[1907]=16453;
+prime_table[1908]=16477;
+prime_table[1909]=16481;
+prime_table[1910]=16487;
+prime_table[1911]=16493;
+prime_table[1912]=16519;
+prime_table[1913]=16529;
+prime_table[1914]=16547;
+prime_table[1915]=16553;
+prime_table[1916]=16561;
+prime_table[1917]=16567;
+prime_table[1918]=16573;
+prime_table[1919]=16603;
+prime_table[1920]=16607;
+prime_table[1921]=16619;
+prime_table[1922]=16631;
+prime_table[1923]=16633;
+prime_table[1924]=16649;
+prime_table[1925]=16651;
+prime_table[1926]=16657;
+prime_table[1927]=16661;
+prime_table[1928]=16673;
+prime_table[1929]=16691;
+prime_table[1930]=16693;
+prime_table[1931]=16699;
+prime_table[1932]=16703;
+prime_table[1933]=16729;
+prime_table[1934]=16741;
+prime_table[1935]=16747;
+prime_table[1936]=16759;
+prime_table[1937]=16763;
+prime_table[1938]=16787;
+prime_table[1939]=16811;
+prime_table[1940]=16823;
+prime_table[1941]=16829;
+prime_table[1942]=16831;
+prime_table[1943]=16843;
+prime_table[1944]=16871;
+prime_table[1945]=16879;
+prime_table[1946]=16883;
+prime_table[1947]=16889;
+prime_table[1948]=16901;
+prime_table[1949]=16903;
+prime_table[1950]=16921;
+prime_table[1951]=16927;
+prime_table[1952]=16931;
+prime_table[1953]=16937;
+prime_table[1954]=16943;
+prime_table[1955]=16963;
+prime_table[1956]=16979;
+prime_table[1957]=16981;
+prime_table[1958]=16987;
+prime_table[1959]=16993;
+prime_table[1960]=17011;
+prime_table[1961]=17021;
+prime_table[1962]=17027;
+prime_table[1963]=17029;
+prime_table[1964]=17033;
+prime_table[1965]=17041;
+prime_table[1966]=17047;
+prime_table[1967]=17053;
+prime_table[1968]=17077;
+prime_table[1969]=17093;
+prime_table[1970]=17099;
+prime_table[1971]=17107;
+prime_table[1972]=17117;
+prime_table[1973]=17123;
+prime_table[1974]=17137;
+prime_table[1975]=17159;
+prime_table[1976]=17167;
+prime_table[1977]=17183;
+prime_table[1978]=17189;
+prime_table[1979]=17191;
+prime_table[1980]=17203;
+prime_table[1981]=17207;
+prime_table[1982]=17209;
+prime_table[1983]=17231;
+prime_table[1984]=17239;
+prime_table[1985]=17257;
+prime_table[1986]=17291;
+prime_table[1987]=17293;
+prime_table[1988]=17299;
+prime_table[1989]=17317;
+prime_table[1990]=17321;
+prime_table[1991]=17327;
+prime_table[1992]=17333;
+prime_table[1993]=17341;
+prime_table[1994]=17351;
+prime_table[1995]=17359;
+prime_table[1996]=17377;
+prime_table[1997]=17383;
+prime_table[1998]=17387;
+prime_table[1999]=17389;
+prime_table[2000]=17393;
+prime_table[2001]=17401;
+prime_table[2002]=17417;
+prime_table[2003]=17419;
+prime_table[2004]=17431;
+prime_table[2005]=17443;
+prime_table[2006]=17449;
+prime_table[2007]=17467;
+prime_table[2008]=17471;
+prime_table[2009]=17477;
+prime_table[2010]=17483;
+prime_table[2011]=17489;
+prime_table[2012]=17491;
+prime_table[2013]=17497;
+prime_table[2014]=17509;
+prime_table[2015]=17519;
+prime_table[2016]=17539;
+prime_table[2017]=17551;
+prime_table[2018]=17569;
+prime_table[2019]=17573;
+prime_table[2020]=17579;
+prime_table[2021]=17581;
+prime_table[2022]=17597;
+prime_table[2023]=17599;
+prime_table[2024]=17609;
+prime_table[2025]=17623;
+prime_table[2026]=17627;
+prime_table[2027]=17657;
+prime_table[2028]=17659;
+prime_table[2029]=17669;
+prime_table[2030]=17681;
+prime_table[2031]=17683;
+prime_table[2032]=17707;
+prime_table[2033]=17713;
+prime_table[2034]=17729;
+prime_table[2035]=17737;
+prime_table[2036]=17747;
+prime_table[2037]=17749;
+prime_table[2038]=17761;
+prime_table[2039]=17783;
+prime_table[2040]=17789;
+prime_table[2041]=17791;
+prime_table[2042]=17807;
+prime_table[2043]=17827;
+prime_table[2044]=17837;
+prime_table[2045]=17839;
+prime_table[2046]=17851;
+prime_table[2047]=17863;
+prime_table[2048]=17881;
+prime_table[2049]=17891;
+prime_table[2050]=17903;
+prime_table[2051]=17909;
+prime_table[2052]=17911;
+prime_table[2053]=17921;
+prime_table[2054]=17923;
+prime_table[2055]=17929;
+prime_table[2056]=17939;
+prime_table[2057]=17957;
+prime_table[2058]=17959;
+prime_table[2059]=17971;
+prime_table[2060]=17977;
+prime_table[2061]=17981;
+prime_table[2062]=17987;
+prime_table[2063]=17989;
+prime_table[2064]=18013;
+prime_table[2065]=18041;
+prime_table[2066]=18043;
+prime_table[2067]=18047;
+prime_table[2068]=18049;
+prime_table[2069]=18059;
+prime_table[2070]=18061;
+prime_table[2071]=18077;
+prime_table[2072]=18089;
+prime_table[2073]=18097;
+prime_table[2074]=18119;
+prime_table[2075]=18121;
+prime_table[2076]=18127;
+prime_table[2077]=18131;
+prime_table[2078]=18133;
+prime_table[2079]=18143;
+prime_table[2080]=18149;
+prime_table[2081]=18169;
+prime_table[2082]=18181;
+prime_table[2083]=18191;
+prime_table[2084]=18199;
+prime_table[2085]=18211;
+prime_table[2086]=18217;
+prime_table[2087]=18223;
+prime_table[2088]=18229;
+prime_table[2089]=18233;
+prime_table[2090]=18251;
+prime_table[2091]=18253;
+prime_table[2092]=18257;
+prime_table[2093]=18269;
+prime_table[2094]=18287;
+prime_table[2095]=18289;
+prime_table[2096]=18301;
+prime_table[2097]=18307;
+prime_table[2098]=18311;
+prime_table[2099]=18313;
+prime_table[2100]=18329;
+prime_table[2101]=18341;
+prime_table[2102]=18353;
+prime_table[2103]=18367;
+prime_table[2104]=18371;
+prime_table[2105]=18379;
+prime_table[2106]=18397;
+prime_table[2107]=18401;
+prime_table[2108]=18413;
+prime_table[2109]=18427;
+prime_table[2110]=18433;
+prime_table[2111]=18439;
+prime_table[2112]=18443;
+prime_table[2113]=18451;
+prime_table[2114]=18457;
+prime_table[2115]=18461;
+prime_table[2116]=18481;
+prime_table[2117]=18493;
+prime_table[2118]=18503;
+prime_table[2119]=18517;
+prime_table[2120]=18521;
+prime_table[2121]=18523;
+prime_table[2122]=18539;
+prime_table[2123]=18541;
+prime_table[2124]=18553;
+prime_table[2125]=18583;
+prime_table[2126]=18587;
+prime_table[2127]=18593;
+prime_table[2128]=18617;
+prime_table[2129]=18637;
+prime_table[2130]=18661;
+prime_table[2131]=18671;
+prime_table[2132]=18679;
+prime_table[2133]=18691;
+prime_table[2134]=18701;
+prime_table[2135]=18713;
+prime_table[2136]=18719;
+prime_table[2137]=18731;
+prime_table[2138]=18743;
+prime_table[2139]=18749;
+prime_table[2140]=18757;
+prime_table[2141]=18773;
+prime_table[2142]=18787;
+prime_table[2143]=18793;
+prime_table[2144]=18797;
+prime_table[2145]=18803;
+prime_table[2146]=18839;
+prime_table[2147]=18859;
+prime_table[2148]=18869;
+prime_table[2149]=18899;
+prime_table[2150]=18911;
+prime_table[2151]=18913;
+prime_table[2152]=18917;
+prime_table[2153]=18919;
+prime_table[2154]=18947;
+prime_table[2155]=18959;
+prime_table[2156]=18973;
+prime_table[2157]=18979;
+prime_table[2158]=19001;
+prime_table[2159]=19009;
+prime_table[2160]=19013;
+prime_table[2161]=19031;
+prime_table[2162]=19037;
+prime_table[2163]=19051;
+prime_table[2164]=19069;
+prime_table[2165]=19073;
+prime_table[2166]=19079;
+prime_table[2167]=19081;
+prime_table[2168]=19087;
+prime_table[2169]=19121;
+prime_table[2170]=19139;
+prime_table[2171]=19141;
+prime_table[2172]=19157;
+prime_table[2173]=19163;
+prime_table[2174]=19181;
+prime_table[2175]=19183;
+prime_table[2176]=19207;
+prime_table[2177]=19211;
+prime_table[2178]=19213;
+prime_table[2179]=19219;
+prime_table[2180]=19231;
+prime_table[2181]=19237;
+prime_table[2182]=19249;
+prime_table[2183]=19259;
+prime_table[2184]=19267;
+prime_table[2185]=19273;
+prime_table[2186]=19289;
+prime_table[2187]=19301;
+prime_table[2188]=19309;
+prime_table[2189]=19319;
+prime_table[2190]=19333;
+prime_table[2191]=19373;
+prime_table[2192]=19379;
+prime_table[2193]=19381;
+prime_table[2194]=19387;
+prime_table[2195]=19391;
+prime_table[2196]=19403;
+prime_table[2197]=19417;
+prime_table[2198]=19421;
+prime_table[2199]=19423;
+prime_table[2200]=19427;
+prime_table[2201]=19429;
+prime_table[2202]=19433;
+prime_table[2203]=19441;
+prime_table[2204]=19447;
+prime_table[2205]=19457;
+prime_table[2206]=19463;
+prime_table[2207]=19469;
+prime_table[2208]=19471;
+prime_table[2209]=19477;
+prime_table[2210]=19483;
+prime_table[2211]=19489;
+prime_table[2212]=19501;
+prime_table[2213]=19507;
+prime_table[2214]=19531;
+prime_table[2215]=19541;
+prime_table[2216]=19543;
+prime_table[2217]=19553;
+prime_table[2218]=19559;
+prime_table[2219]=19571;
+prime_table[2220]=19577;
+prime_table[2221]=19583;
+prime_table[2222]=19597;
+prime_table[2223]=19603;
+prime_table[2224]=19609;
+prime_table[2225]=19661;
+prime_table[2226]=19681;
+prime_table[2227]=19687;
+prime_table[2228]=19697;
+prime_table[2229]=19699;
+prime_table[2230]=19709;
+prime_table[2231]=19717;
+prime_table[2232]=19727;
+prime_table[2233]=19739;
+prime_table[2234]=19751;
+prime_table[2235]=19753;
+prime_table[2236]=19759;
+prime_table[2237]=19763;
+prime_table[2238]=19777;
+prime_table[2239]=19793;
+prime_table[2240]=19801;
+prime_table[2241]=19813;
+prime_table[2242]=19819;
+prime_table[2243]=19841;
+prime_table[2244]=19843;
+prime_table[2245]=19853;
+prime_table[2246]=19861;
+prime_table[2247]=19867;
+prime_table[2248]=19889;
+prime_table[2249]=19891;
+prime_table[2250]=19913;
+prime_table[2251]=19919;
+prime_table[2252]=19927;
+prime_table[2253]=19937;
+prime_table[2254]=19949;
+prime_table[2255]=19961;
+prime_table[2256]=19963;
+prime_table[2257]=19973;
+prime_table[2258]=19979;
+prime_table[2259]=19991;
+prime_table[2260]=19993;
+prime_table[2261]=19997;
+prime_table[2262]=20011;
+prime_table[2263]=20021;
+prime_table[2264]=20023;
+prime_table[2265]=20029;
+prime_table[2266]=20047;
+prime_table[2267]=20051;
+prime_table[2268]=20063;
+prime_table[2269]=20071;
+prime_table[2270]=20089;
+prime_table[2271]=20101;
+prime_table[2272]=20107;
+prime_table[2273]=20113;
+prime_table[2274]=20117;
+prime_table[2275]=20123;
+prime_table[2276]=20129;
+prime_table[2277]=20143;
+prime_table[2278]=20147;
+prime_table[2279]=20149;
+prime_table[2280]=20161;
+prime_table[2281]=20173;
+prime_table[2282]=20177;
+prime_table[2283]=20183;
+prime_table[2284]=20201;
+prime_table[2285]=20219;
+prime_table[2286]=20231;
+prime_table[2287]=20233;
+prime_table[2288]=20249;
+prime_table[2289]=20261;
+prime_table[2290]=20269;
+prime_table[2291]=20287;
+prime_table[2292]=20297;
+prime_table[2293]=20323;
+prime_table[2294]=20327;
+prime_table[2295]=20333;
+prime_table[2296]=20341;
+prime_table[2297]=20347;
+prime_table[2298]=20353;
+prime_table[2299]=20357;
+prime_table[2300]=20359;
+prime_table[2301]=20369;
+prime_table[2302]=20389;
+prime_table[2303]=20393;
+prime_table[2304]=20399;
+prime_table[2305]=20407;
+prime_table[2306]=20411;
+prime_table[2307]=20431;
+prime_table[2308]=20441;
+prime_table[2309]=20443;
+prime_table[2310]=20477;
+prime_table[2311]=20479;
+prime_table[2312]=20483;
+prime_table[2313]=20507;
+prime_table[2314]=20509;
+prime_table[2315]=20521;
+prime_table[2316]=20533;
+prime_table[2317]=20543;
+prime_table[2318]=20549;
+prime_table[2319]=20551;
+prime_table[2320]=20563;
+prime_table[2321]=20593;
+prime_table[2322]=20599;
+prime_table[2323]=20611;
+prime_table[2324]=20627;
+prime_table[2325]=20639;
+prime_table[2326]=20641;
+prime_table[2327]=20663;
+prime_table[2328]=20681;
+prime_table[2329]=20693;
+prime_table[2330]=20707;
+prime_table[2331]=20717;
+prime_table[2332]=20719;
+prime_table[2333]=20731;
+prime_table[2334]=20743;
+prime_table[2335]=20747;
+prime_table[2336]=20749;
+prime_table[2337]=20753;
+prime_table[2338]=20759;
+prime_table[2339]=20771;
+prime_table[2340]=20773;
+prime_table[2341]=20789;
+prime_table[2342]=20807;
+prime_table[2343]=20809;
+prime_table[2344]=20849;
+prime_table[2345]=20857;
+prime_table[2346]=20873;
+prime_table[2347]=20879;
+prime_table[2348]=20887;
+prime_table[2349]=20897;
+prime_table[2350]=20899;
+prime_table[2351]=20903;
+prime_table[2352]=20921;
+prime_table[2353]=20929;
+prime_table[2354]=20939;
+prime_table[2355]=20947;
+prime_table[2356]=20959;
+prime_table[2357]=20963;
+prime_table[2358]=20981;
+prime_table[2359]=20983;
+prime_table[2360]=21001;
+prime_table[2361]=21011;
+prime_table[2362]=21013;
+prime_table[2363]=21017;
+prime_table[2364]=21019;
+prime_table[2365]=21023;
+prime_table[2366]=21031;
+prime_table[2367]=21059;
+prime_table[2368]=21061;
+prime_table[2369]=21067;
+prime_table[2370]=21089;
+prime_table[2371]=21101;
+prime_table[2372]=21107;
+prime_table[2373]=21121;
+prime_table[2374]=21139;
+prime_table[2375]=21143;
+prime_table[2376]=21149;
+prime_table[2377]=21157;
+prime_table[2378]=21163;
+prime_table[2379]=21169;
+prime_table[2380]=21179;
+prime_table[2381]=21187;
+prime_table[2382]=21191;
+prime_table[2383]=21193;
+prime_table[2384]=21211;
+prime_table[2385]=21221;
+prime_table[2386]=21227;
+prime_table[2387]=21247;
+prime_table[2388]=21269;
+prime_table[2389]=21277;
+prime_table[2390]=21283;
+prime_table[2391]=21313;
+prime_table[2392]=21317;
+prime_table[2393]=21319;
+prime_table[2394]=21323;
+prime_table[2395]=21341;
+prime_table[2396]=21347;
+prime_table[2397]=21377;
+prime_table[2398]=21379;
+prime_table[2399]=21383;
+prime_table[2400]=21391;
+prime_table[2401]=21397;
+prime_table[2402]=21401;
+prime_table[2403]=21407;
+prime_table[2404]=21419;
+prime_table[2405]=21433;
+prime_table[2406]=21467;
+prime_table[2407]=21481;
+prime_table[2408]=21487;
+prime_table[2409]=21491;
+prime_table[2410]=21493;
+prime_table[2411]=21499;
+prime_table[2412]=21503;
+prime_table[2413]=21517;
+prime_table[2414]=21521;
+prime_table[2415]=21523;
+prime_table[2416]=21529;
+prime_table[2417]=21557;
+prime_table[2418]=21559;
+prime_table[2419]=21563;
+prime_table[2420]=21569;
+prime_table[2421]=21577;
+prime_table[2422]=21587;
+prime_table[2423]=21589;
+prime_table[2424]=21599;
+prime_table[2425]=21601;
+prime_table[2426]=21611;
+prime_table[2427]=21613;
+prime_table[2428]=21617;
+prime_table[2429]=21647;
+prime_table[2430]=21649;
+prime_table[2431]=21661;
+prime_table[2432]=21673;
+prime_table[2433]=21683;
+prime_table[2434]=21701;
+prime_table[2435]=21713;
+prime_table[2436]=21727;
+prime_table[2437]=21737;
+prime_table[2438]=21739;
+prime_table[2439]=21751;
+prime_table[2440]=21757;
+prime_table[2441]=21767;
+prime_table[2442]=21773;
+prime_table[2443]=21787;
+prime_table[2444]=21799;
+prime_table[2445]=21803;
+prime_table[2446]=21817;
+prime_table[2447]=21821;
+prime_table[2448]=21839;
+prime_table[2449]=21841;
+prime_table[2450]=21851;
+prime_table[2451]=21859;
+prime_table[2452]=21863;
+prime_table[2453]=21871;
+prime_table[2454]=21881;
+prime_table[2455]=21893;
+prime_table[2456]=21911;
+prime_table[2457]=21929;
+prime_table[2458]=21937;
+prime_table[2459]=21943;
+prime_table[2460]=21961;
+prime_table[2461]=21977;
+prime_table[2462]=21991;
+prime_table[2463]=21997;
+prime_table[2464]=22003;
+prime_table[2465]=22013;
+prime_table[2466]=22027;
+prime_table[2467]=22031;
+prime_table[2468]=22037;
+prime_table[2469]=22039;
+prime_table[2470]=22051;
+prime_table[2471]=22063;
+prime_table[2472]=22067;
+prime_table[2473]=22073;
+prime_table[2474]=22079;
+prime_table[2475]=22091;
+prime_table[2476]=22093;
+prime_table[2477]=22109;
+prime_table[2478]=22111;
+prime_table[2479]=22123;
+prime_table[2480]=22129;
+prime_table[2481]=22133;
+prime_table[2482]=22147;
+prime_table[2483]=22153;
+prime_table[2484]=22157;
+prime_table[2485]=22159;
+prime_table[2486]=22171;
+prime_table[2487]=22189;
+prime_table[2488]=22193;
+prime_table[2489]=22229;
+prime_table[2490]=22247;
+prime_table[2491]=22259;
+prime_table[2492]=22271;
+prime_table[2493]=22273;
+prime_table[2494]=22277;
+prime_table[2495]=22279;
+prime_table[2496]=22283;
+prime_table[2497]=22291;
+prime_table[2498]=22303;
+prime_table[2499]=22307;
+prime_table[2500]=22343;
+prime_table[2501]=22349;
+prime_table[2502]=22367;
+prime_table[2503]=22369;
+prime_table[2504]=22381;
+prime_table[2505]=22391;
+prime_table[2506]=22397;
+prime_table[2507]=22409;
+prime_table[2508]=22433;
+prime_table[2509]=22441;
+prime_table[2510]=22447;
+prime_table[2511]=22453;
+prime_table[2512]=22469;
+prime_table[2513]=22481;
+prime_table[2514]=22483;
+prime_table[2515]=22501;
+prime_table[2516]=22511;
+prime_table[2517]=22531;
+prime_table[2518]=22541;
+prime_table[2519]=22543;
+prime_table[2520]=22549;
+prime_table[2521]=22567;
+prime_table[2522]=22571;
+prime_table[2523]=22573;
+prime_table[2524]=22613;
+prime_table[2525]=22619;
+prime_table[2526]=22621;
+prime_table[2527]=22637;
+prime_table[2528]=22639;
+prime_table[2529]=22643;
+prime_table[2530]=22651;
+prime_table[2531]=22669;
+prime_table[2532]=22679;
+prime_table[2533]=22691;
+prime_table[2534]=22697;
+prime_table[2535]=22699;
+prime_table[2536]=22709;
+prime_table[2537]=22717;
+prime_table[2538]=22721;
+prime_table[2539]=22727;
+prime_table[2540]=22739;
+prime_table[2541]=22741;
+prime_table[2542]=22751;
+prime_table[2543]=22769;
+prime_table[2544]=22777;
+prime_table[2545]=22783;
+prime_table[2546]=22787;
+prime_table[2547]=22807;
+prime_table[2548]=22811;
+prime_table[2549]=22817;
+prime_table[2550]=22853;
+prime_table[2551]=22859;
+prime_table[2552]=22861;
+prime_table[2553]=22871;
+prime_table[2554]=22877;
+prime_table[2555]=22901;
+prime_table[2556]=22907;
+prime_table[2557]=22921;
+prime_table[2558]=22937;
+prime_table[2559]=22943;
+prime_table[2560]=22961;
+prime_table[2561]=22963;
+prime_table[2562]=22973;
+prime_table[2563]=22993;
+prime_table[2564]=23003;
+prime_table[2565]=23011;
+prime_table[2566]=23017;
+prime_table[2567]=23021;
+prime_table[2568]=23027;
+prime_table[2569]=23029;
+prime_table[2570]=23039;
+prime_table[2571]=23041;
+prime_table[2572]=23053;
+prime_table[2573]=23057;
+prime_table[2574]=23059;
+prime_table[2575]=23063;
+prime_table[2576]=23071;
+prime_table[2577]=23081;
+prime_table[2578]=23087;
+prime_table[2579]=23099;
+prime_table[2580]=23117;
+prime_table[2581]=23131;
+prime_table[2582]=23143;
+prime_table[2583]=23159;
+prime_table[2584]=23167;
+prime_table[2585]=23173;
+prime_table[2586]=23189;
+prime_table[2587]=23197;
+prime_table[2588]=23201;
+prime_table[2589]=23203;
+prime_table[2590]=23209;
+prime_table[2591]=23227;
+prime_table[2592]=23251;
+prime_table[2593]=23269;
+prime_table[2594]=23279;
+prime_table[2595]=23291;
+prime_table[2596]=23293;
+prime_table[2597]=23297;
+prime_table[2598]=23311;
+prime_table[2599]=23321;
+prime_table[2600]=23327;
+prime_table[2601]=23333;
+prime_table[2602]=23339;
+prime_table[2603]=23357;
+prime_table[2604]=23369;
+prime_table[2605]=23371;
+prime_table[2606]=23399;
+prime_table[2607]=23417;
+prime_table[2608]=23431;
+prime_table[2609]=23447;
+prime_table[2610]=23459;
+prime_table[2611]=23473;
+prime_table[2612]=23497;
+prime_table[2613]=23509;
+prime_table[2614]=23531;
+prime_table[2615]=23537;
+prime_table[2616]=23539;
+prime_table[2617]=23549;
+prime_table[2618]=23557;
+prime_table[2619]=23561;
+prime_table[2620]=23563;
+prime_table[2621]=23567;
+prime_table[2622]=23581;
+prime_table[2623]=23593;
+prime_table[2624]=23599;
+prime_table[2625]=23603;
+prime_table[2626]=23609;
+prime_table[2627]=23623;
+prime_table[2628]=23627;
+prime_table[2629]=23629;
+prime_table[2630]=23633;
+prime_table[2631]=23663;
+prime_table[2632]=23669;
+prime_table[2633]=23671;
+prime_table[2634]=23677;
+prime_table[2635]=23687;
+prime_table[2636]=23689;
+prime_table[2637]=23719;
+prime_table[2638]=23741;
+prime_table[2639]=23743;
+prime_table[2640]=23747;
+prime_table[2641]=23753;
+prime_table[2642]=23761;
+prime_table[2643]=23767;
+prime_table[2644]=23773;
+prime_table[2645]=23789;
+prime_table[2646]=23801;
+prime_table[2647]=23813;
+prime_table[2648]=23819;
+prime_table[2649]=23827;
+prime_table[2650]=23831;
+prime_table[2651]=23833;
+prime_table[2652]=23857;
+prime_table[2653]=23869;
+prime_table[2654]=23873;
+prime_table[2655]=23879;
+prime_table[2656]=23887;
+prime_table[2657]=23893;
+prime_table[2658]=23899;
+prime_table[2659]=23909;
+prime_table[2660]=23911;
+prime_table[2661]=23917;
+prime_table[2662]=23929;
+prime_table[2663]=23957;
+prime_table[2664]=23971;
+prime_table[2665]=23977;
+prime_table[2666]=23981;
+prime_table[2667]=23993;
+prime_table[2668]=24001;
+prime_table[2669]=24007;
+prime_table[2670]=24019;
+prime_table[2671]=24023;
+prime_table[2672]=24029;
+prime_table[2673]=24043;
+prime_table[2674]=24049;
+prime_table[2675]=24061;
+prime_table[2676]=24071;
+prime_table[2677]=24077;
+prime_table[2678]=24083;
+prime_table[2679]=24091;
+prime_table[2680]=24097;
+prime_table[2681]=24103;
+prime_table[2682]=24107;
+prime_table[2683]=24109;
+prime_table[2684]=24113;
+prime_table[2685]=24121;
+prime_table[2686]=24133;
+prime_table[2687]=24137;
+prime_table[2688]=24151;
+prime_table[2689]=24169;
+prime_table[2690]=24179;
+prime_table[2691]=24181;
+prime_table[2692]=24197;
+prime_table[2693]=24203;
+prime_table[2694]=24223;
+prime_table[2695]=24229;
+prime_table[2696]=24239;
+prime_table[2697]=24247;
+prime_table[2698]=24251;
+prime_table[2699]=24281;
+prime_table[2700]=24317;
+prime_table[2701]=24329;
+prime_table[2702]=24337;
+prime_table[2703]=24359;
+prime_table[2704]=24371;
+prime_table[2705]=24373;
+prime_table[2706]=24379;
+prime_table[2707]=24391;
+prime_table[2708]=24407;
+prime_table[2709]=24413;
+prime_table[2710]=24419;
+prime_table[2711]=24421;
+prime_table[2712]=24439;
+prime_table[2713]=24443;
+prime_table[2714]=24469;
+prime_table[2715]=24473;
+prime_table[2716]=24481;
+prime_table[2717]=24499;
+prime_table[2718]=24509;
+prime_table[2719]=24517;
+prime_table[2720]=24527;
+prime_table[2721]=24533;
+prime_table[2722]=24547;
+prime_table[2723]=24551;
+prime_table[2724]=24571;
+prime_table[2725]=24593;
+prime_table[2726]=24611;
+prime_table[2727]=24623;
+prime_table[2728]=24631;
+prime_table[2729]=24659;
+prime_table[2730]=24671;
+prime_table[2731]=24677;
+prime_table[2732]=24683;
+prime_table[2733]=24691;
+prime_table[2734]=24697;
+prime_table[2735]=24709;
+prime_table[2736]=24733;
+prime_table[2737]=24749;
+prime_table[2738]=24763;
+prime_table[2739]=24767;
+prime_table[2740]=24781;
+prime_table[2741]=24793;
+prime_table[2742]=24799;
+prime_table[2743]=24809;
+prime_table[2744]=24821;
+prime_table[2745]=24841;
+prime_table[2746]=24847;
+prime_table[2747]=24851;
+prime_table[2748]=24859;
+prime_table[2749]=24877;
+prime_table[2750]=24889;
+prime_table[2751]=24907;
+prime_table[2752]=24917;
+prime_table[2753]=24919;
+prime_table[2754]=24923;
+prime_table[2755]=24943;
+prime_table[2756]=24953;
+prime_table[2757]=24967;
+prime_table[2758]=24971;
+prime_table[2759]=24977;
+prime_table[2760]=24979;
+prime_table[2761]=24989;
+prime_table[2762]=25013;
+prime_table[2763]=25031;
+prime_table[2764]=25033;
+prime_table[2765]=25037;
+prime_table[2766]=25057;
+prime_table[2767]=25073;
+prime_table[2768]=25087;
+prime_table[2769]=25097;
+prime_table[2770]=25111;
+prime_table[2771]=25117;
+prime_table[2772]=25121;
+prime_table[2773]=25127;
+prime_table[2774]=25147;
+prime_table[2775]=25153;
+prime_table[2776]=25163;
+prime_table[2777]=25169;
+prime_table[2778]=25171;
+prime_table[2779]=25183;
+prime_table[2780]=25189;
+prime_table[2781]=25219;
+prime_table[2782]=25229;
+prime_table[2783]=25237;
+prime_table[2784]=25243;
+prime_table[2785]=25247;
+prime_table[2786]=25253;
+prime_table[2787]=25261;
+prime_table[2788]=25301;
+prime_table[2789]=25303;
+prime_table[2790]=25307;
+prime_table[2791]=25309;
+prime_table[2792]=25321;
+prime_table[2793]=25339;
+prime_table[2794]=25343;
+prime_table[2795]=25349;
+prime_table[2796]=25357;
+prime_table[2797]=25367;
+prime_table[2798]=25373;
+prime_table[2799]=25391;
+prime_table[2800]=25409;
+prime_table[2801]=25411;
+prime_table[2802]=25423;
+prime_table[2803]=25439;
+prime_table[2804]=25447;
+prime_table[2805]=25453;
+prime_table[2806]=25457;
+prime_table[2807]=25463;
+prime_table[2808]=25469;
+prime_table[2809]=25471;
+prime_table[2810]=25523;
+prime_table[2811]=25537;
+prime_table[2812]=25541;
+prime_table[2813]=25561;
+prime_table[2814]=25577;
+prime_table[2815]=25579;
+prime_table[2816]=25583;
+prime_table[2817]=25589;
+prime_table[2818]=25601;
+prime_table[2819]=25603;
+prime_table[2820]=25609;
+prime_table[2821]=25621;
+prime_table[2822]=25633;
+prime_table[2823]=25639;
+prime_table[2824]=25643;
+prime_table[2825]=25657;
+prime_table[2826]=25667;
+prime_table[2827]=25673;
+prime_table[2828]=25679;
+prime_table[2829]=25693;
+prime_table[2830]=25703;
+prime_table[2831]=25717;
+prime_table[2832]=25733;
+prime_table[2833]=25741;
+prime_table[2834]=25747;
+prime_table[2835]=25759;
+prime_table[2836]=25763;
+prime_table[2837]=25771;
+prime_table[2838]=25793;
+prime_table[2839]=25799;
+prime_table[2840]=25801;
+prime_table[2841]=25819;
+prime_table[2842]=25841;
+prime_table[2843]=25847;
+prime_table[2844]=25849;
+prime_table[2845]=25867;
+prime_table[2846]=25873;
+prime_table[2847]=25889;
+prime_table[2848]=25903;
+prime_table[2849]=25913;
+prime_table[2850]=25919;
+prime_table[2851]=25931;
+prime_table[2852]=25933;
+prime_table[2853]=25939;
+prime_table[2854]=25943;
+prime_table[2855]=25951;
+prime_table[2856]=25969;
+prime_table[2857]=25981;
+prime_table[2858]=25997;
+prime_table[2859]=25999;
+prime_table[2860]=26003;
+prime_table[2861]=26017;
+prime_table[2862]=26021;
+prime_table[2863]=26029;
+prime_table[2864]=26041;
+prime_table[2865]=26053;
+prime_table[2866]=26083;
+prime_table[2867]=26099;
+prime_table[2868]=26107;
+prime_table[2869]=26111;
+prime_table[2870]=26113;
+prime_table[2871]=26119;
+prime_table[2872]=26141;
+prime_table[2873]=26153;
+prime_table[2874]=26161;
+prime_table[2875]=26171;
+prime_table[2876]=26177;
+prime_table[2877]=26183;
+prime_table[2878]=26189;
+prime_table[2879]=26203;
+prime_table[2880]=26209;
+prime_table[2881]=26227;
+prime_table[2882]=26237;
+prime_table[2883]=26249;
+prime_table[2884]=26251;
+prime_table[2885]=26261;
+prime_table[2886]=26263;
+prime_table[2887]=26267;
+prime_table[2888]=26293;
+prime_table[2889]=26297;
+prime_table[2890]=26309;
+prime_table[2891]=26317;
+prime_table[2892]=26321;
+prime_table[2893]=26339;
+prime_table[2894]=26347;
+prime_table[2895]=26357;
+prime_table[2896]=26371;
+prime_table[2897]=26387;
+prime_table[2898]=26393;
+prime_table[2899]=26399;
+prime_table[2900]=26407;
+prime_table[2901]=26417;
+prime_table[2902]=26423;
+prime_table[2903]=26431;
+prime_table[2904]=26437;
+prime_table[2905]=26449;
+prime_table[2906]=26459;
+prime_table[2907]=26479;
+prime_table[2908]=26489;
+prime_table[2909]=26497;
+prime_table[2910]=26501;
+prime_table[2911]=26513;
+prime_table[2912]=26539;
+prime_table[2913]=26557;
+prime_table[2914]=26561;
+prime_table[2915]=26573;
+prime_table[2916]=26591;
+prime_table[2917]=26597;
+prime_table[2918]=26627;
+prime_table[2919]=26633;
+prime_table[2920]=26641;
+prime_table[2921]=26647;
+prime_table[2922]=26669;
+prime_table[2923]=26681;
+prime_table[2924]=26683;
+prime_table[2925]=26687;
+prime_table[2926]=26693;
+prime_table[2927]=26699;
+prime_table[2928]=26701;
+prime_table[2929]=26711;
+prime_table[2930]=26713;
+prime_table[2931]=26717;
+prime_table[2932]=26723;
+prime_table[2933]=26729;
+prime_table[2934]=26731;
+prime_table[2935]=26737;
+prime_table[2936]=26759;
+prime_table[2937]=26777;
+prime_table[2938]=26783;
+prime_table[2939]=26801;
+prime_table[2940]=26813;
+prime_table[2941]=26821;
+prime_table[2942]=26833;
+prime_table[2943]=26839;
+prime_table[2944]=26849;
+prime_table[2945]=26861;
+prime_table[2946]=26863;
+prime_table[2947]=26879;
+prime_table[2948]=26881;
+prime_table[2949]=26891;
+prime_table[2950]=26893;
+prime_table[2951]=26903;
+prime_table[2952]=26921;
+prime_table[2953]=26927;
+prime_table[2954]=26947;
+prime_table[2955]=26951;
+prime_table[2956]=26953;
+prime_table[2957]=26959;
+prime_table[2958]=26981;
+prime_table[2959]=26987;
+prime_table[2960]=26993;
+prime_table[2961]=27011;
+prime_table[2962]=27017;
+prime_table[2963]=27031;
+prime_table[2964]=27043;
+prime_table[2965]=27059;
+prime_table[2966]=27061;
+prime_table[2967]=27067;
+prime_table[2968]=27073;
+prime_table[2969]=27077;
+prime_table[2970]=27091;
+prime_table[2971]=27103;
+prime_table[2972]=27107;
+prime_table[2973]=27109;
+prime_table[2974]=27127;
+prime_table[2975]=27143;
+prime_table[2976]=27179;
+prime_table[2977]=27191;
+prime_table[2978]=27197;
+prime_table[2979]=27211;
+prime_table[2980]=27239;
+prime_table[2981]=27241;
+prime_table[2982]=27253;
+prime_table[2983]=27259;
+prime_table[2984]=27271;
+prime_table[2985]=27277;
+prime_table[2986]=27281;
+prime_table[2987]=27283;
+prime_table[2988]=27299;
+prime_table[2989]=27329;
+prime_table[2990]=27337;
+prime_table[2991]=27361;
+prime_table[2992]=27367;
+prime_table[2993]=27397;
+prime_table[2994]=27407;
+prime_table[2995]=27409;
+prime_table[2996]=27427;
+prime_table[2997]=27431;
+prime_table[2998]=27437;
+prime_table[2999]=27449;
+prime_table[3000]=27457;
+prime_table[3001]=27479;
+prime_table[3002]=27481;
+prime_table[3003]=27487;
+prime_table[3004]=27509;
+prime_table[3005]=27527;
+prime_table[3006]=27529;
+prime_table[3007]=27539;
+prime_table[3008]=27541;
+prime_table[3009]=27551;
+prime_table[3010]=27581;
+prime_table[3011]=27583;
+prime_table[3012]=27611;
+prime_table[3013]=27617;
+prime_table[3014]=27631;
+prime_table[3015]=27647;
+prime_table[3016]=27653;
+prime_table[3017]=27673;
+prime_table[3018]=27689;
+prime_table[3019]=27691;
+prime_table[3020]=27697;
+prime_table[3021]=27701;
+prime_table[3022]=27733;
+prime_table[3023]=27737;
+prime_table[3024]=27739;
+prime_table[3025]=27743;
+prime_table[3026]=27749;
+prime_table[3027]=27751;
+prime_table[3028]=27763;
+prime_table[3029]=27767;
+prime_table[3030]=27773;
+prime_table[3031]=27779;
+prime_table[3032]=27791;
+prime_table[3033]=27793;
+prime_table[3034]=27799;
+prime_table[3035]=27803;
+prime_table[3036]=27809;
+prime_table[3037]=27817;
+prime_table[3038]=27823;
+prime_table[3039]=27827;
+prime_table[3040]=27847;
+prime_table[3041]=27851;
+prime_table[3042]=27883;
+prime_table[3043]=27893;
+prime_table[3044]=27901;
+prime_table[3045]=27917;
+prime_table[3046]=27919;
+prime_table[3047]=27941;
+prime_table[3048]=27943;
+prime_table[3049]=27947;
+prime_table[3050]=27953;
+prime_table[3051]=27961;
+prime_table[3052]=27967;
+prime_table[3053]=27983;
+prime_table[3054]=27997;
+prime_table[3055]=28001;
+prime_table[3056]=28019;
+prime_table[3057]=28027;
+prime_table[3058]=28031;
+prime_table[3059]=28051;
+prime_table[3060]=28057;
+prime_table[3061]=28069;
+prime_table[3062]=28081;
+prime_table[3063]=28087;
+prime_table[3064]=28097;
+prime_table[3065]=28099;
+prime_table[3066]=28109;
+prime_table[3067]=28111;
+prime_table[3068]=28123;
+prime_table[3069]=28151;
+prime_table[3070]=28163;
+prime_table[3071]=28181;
+prime_table[3072]=28183;
+prime_table[3073]=28201;
+prime_table[3074]=28211;
+prime_table[3075]=28219;
+prime_table[3076]=28229;
+prime_table[3077]=28277;
+prime_table[3078]=28279;
+prime_table[3079]=28283;
+prime_table[3080]=28289;
+prime_table[3081]=28297;
+prime_table[3082]=28307;
+prime_table[3083]=28309;
+prime_table[3084]=28319;
+prime_table[3085]=28349;
+prime_table[3086]=28351;
+prime_table[3087]=28387;
+prime_table[3088]=28393;
+prime_table[3089]=28403;
+prime_table[3090]=28409;
+prime_table[3091]=28411;
+prime_table[3092]=28429;
+prime_table[3093]=28433;
+prime_table[3094]=28439;
+prime_table[3095]=28447;
+prime_table[3096]=28463;
+prime_table[3097]=28477;
+prime_table[3098]=28493;
+prime_table[3099]=28499;
+prime_table[3100]=28513;
+prime_table[3101]=28517;
+prime_table[3102]=28537;
+prime_table[3103]=28541;
+prime_table[3104]=28547;
+prime_table[3105]=28549;
+prime_table[3106]=28559;
+prime_table[3107]=28571;
+prime_table[3108]=28573;
+prime_table[3109]=28579;
+prime_table[3110]=28591;
+prime_table[3111]=28597;
+prime_table[3112]=28603;
+prime_table[3113]=28607;
+prime_table[3114]=28619;
+prime_table[3115]=28621;
+prime_table[3116]=28627;
+prime_table[3117]=28631;
+prime_table[3118]=28643;
+prime_table[3119]=28649;
+prime_table[3120]=28657;
+prime_table[3121]=28661;
+prime_table[3122]=28663;
+prime_table[3123]=28669;
+prime_table[3124]=28687;
+prime_table[3125]=28697;
+prime_table[3126]=28703;
+prime_table[3127]=28711;
+prime_table[3128]=28723;
+prime_table[3129]=28729;
+prime_table[3130]=28751;
+prime_table[3131]=28753;
+prime_table[3132]=28759;
+prime_table[3133]=28771;
+prime_table[3134]=28789;
+prime_table[3135]=28793;
+prime_table[3136]=28807;
+prime_table[3137]=28813;
+prime_table[3138]=28817;
+prime_table[3139]=28837;
+prime_table[3140]=28843;
+prime_table[3141]=28859;
+prime_table[3142]=28867;
+prime_table[3143]=28871;
+prime_table[3144]=28879;
+prime_table[3145]=28901;
+prime_table[3146]=28909;
+prime_table[3147]=28921;
+prime_table[3148]=28927;
+prime_table[3149]=28933;
+prime_table[3150]=28949;
+prime_table[3151]=28961;
+prime_table[3152]=28979;
+prime_table[3153]=29009;
+prime_table[3154]=29017;
+prime_table[3155]=29021;
+prime_table[3156]=29023;
+prime_table[3157]=29027;
+prime_table[3158]=29033;
+prime_table[3159]=29059;
+prime_table[3160]=29063;
+prime_table[3161]=29077;
+prime_table[3162]=29101;
+prime_table[3163]=29123;
+prime_table[3164]=29129;
+prime_table[3165]=29131;
+prime_table[3166]=29137;
+prime_table[3167]=29147;
+prime_table[3168]=29153;
+prime_table[3169]=29167;
+prime_table[3170]=29173;
+prime_table[3171]=29179;
+prime_table[3172]=29191;
+prime_table[3173]=29201;
+prime_table[3174]=29207;
+prime_table[3175]=29209;
+prime_table[3176]=29221;
+prime_table[3177]=29231;
+prime_table[3178]=29243;
+prime_table[3179]=29251;
+prime_table[3180]=29269;
+prime_table[3181]=29287;
+prime_table[3182]=29297;
+prime_table[3183]=29303;
+prime_table[3184]=29311;
+prime_table[3185]=29327;
+prime_table[3186]=29333;
+prime_table[3187]=29339;
+prime_table[3188]=29347;
+prime_table[3189]=29363;
+prime_table[3190]=29383;
+prime_table[3191]=29387;
+prime_table[3192]=29389;
+prime_table[3193]=29399;
+prime_table[3194]=29401;
+prime_table[3195]=29411;
+prime_table[3196]=29423;
+prime_table[3197]=29429;
+prime_table[3198]=29437;
+prime_table[3199]=29443;
+prime_table[3200]=29453;
+prime_table[3201]=29473;
+prime_table[3202]=29483;
+prime_table[3203]=29501;
+prime_table[3204]=29527;
+prime_table[3205]=29531;
+prime_table[3206]=29537;
+prime_table[3207]=29567;
+prime_table[3208]=29569;
+prime_table[3209]=29573;
+prime_table[3210]=29581;
+prime_table[3211]=29587;
+prime_table[3212]=29599;
+prime_table[3213]=29611;
+prime_table[3214]=29629;
+prime_table[3215]=29633;
+prime_table[3216]=29641;
+prime_table[3217]=29663;
+prime_table[3218]=29669;
+prime_table[3219]=29671;
+prime_table[3220]=29683;
+prime_table[3221]=29717;
+prime_table[3222]=29723;
+prime_table[3223]=29741;
+prime_table[3224]=29753;
+prime_table[3225]=29759;
+prime_table[3226]=29761;
+prime_table[3227]=29789;
+prime_table[3228]=29803;
+prime_table[3229]=29819;
+prime_table[3230]=29833;
+prime_table[3231]=29837;
+prime_table[3232]=29851;
+prime_table[3233]=29863;
+prime_table[3234]=29867;
+prime_table[3235]=29873;
+prime_table[3236]=29879;
+prime_table[3237]=29881;
+prime_table[3238]=29917;
+prime_table[3239]=29921;
+prime_table[3240]=29927;
+prime_table[3241]=29947;
+prime_table[3242]=29959;
+prime_table[3243]=29983;
+prime_table[3244]=29989;
+
+ }
+ // Accessor functions.
+ RealType total()const
+ {
+ return m_N;
+ }
+
+ RealType defective()const
+ {
+ return m_n;
+ }
+
+ RealType sample_count()const
+ {
+ return m_r;
+ }
+
+ public:
+ // Data members:
+ RealType m_n; // number of "defective" items
+ RealType m_N; // number of "total" items
+ RealType m_r; // number of items picked
+
+ bool m_gamma,m_tail_recurrence,m_compute_direct_h_x; // use lgamma (true) /factorization (false) method
+ }; // class hypergeometric_distribution
+
+
+
+
+
+ template <class RealType, class Policy>
+ inline long double pdf(const hypergeometric_distribution<RealType, Policy>& dist, const RealType& x)
+ {
+
+ RealType N = dist.total();
+ RealType n = dist.defective();
+ RealType r= dist.sample_count();
+ long double h_x;
+ if(x<std::max(0,r-N+n) || x>std::min(r,n))
+ return 0L;
+ if(dist.m_compute_direct_h_x) {
+ RealType num=1,denom=1;
+
+ boost::array<RealType,9> factorials;
+ factorials[0]=n;factorials[1]=r;factorials[2]=N-n;factorials[3]=N-r;
+ factorials[4]=N;factorials[5]=x;factorials[6]=n-x;factorials[7]=r-x;factorials[8]=N-n-r+x;
+ if(dist.m_gamma) {
+ long double temp=0;
+ for(int i=0;i<4;i++) {
+ temp+=boost::math::lgamma(factorials[i]+1);
+ }
+ for(int i=4;i<9;i++) {
+ temp-=boost::math::lgamma(factorials[i]+1);
+ }
+
+ return std::exp(temp);
+
+ }
+ else{
+ RealType check=factorials[0];
+ //cout<<factorials[0]<<endl;
+ for(int i=1;i<9;i++) {
+ //cout<<factorials[i]<<endl;
+ if(factorials[i]>check)
+ check=factorials[i];
+ }
+ //cout<<check<<endl;
+ vector<RealType> numerator;
+ vector<RealType> denominator;
+ for(int index_of_prime=0;index_of_prime<prime_table.size() && prime_table[index_of_prime]<=check;++index_of_prime) {
+
+ RealType exponent=0;
+ for(int i=0;i<4;i++)
+ exponent+=boost::math::detail::exponent_of_prime(factorials[i],prime_table[index_of_prime]);
+
+ for(int i=4;i<9;i++)
+ exponent-=boost::math::detail::exponent_of_prime(factorials[i],prime_table[index_of_prime]);
+ //cout<<exponent<<endl;
+
+
+ if(exponent==0)
+ continue;
+ RealType prime=prime_table[index_of_prime];
+
+ //compute numerator and denominator, and check for overflow
+
+
+ if(exponent>0)
+ for(RealType j=0;j<exponent;j++) {
+ if((num*prime)/prime==num)
+ num*=prime;
+ else {
+ numerator.push_back(num);
+ num=1;
+ num*=prime;
+ //cout<<num<<":"<<denom<<":"<<mul<<endl;
+ }
+ }
+ else
+ for(RealType j=0;j>exponent;j--) {
+ if((denom*prime)/prime==denom)
+ denom*=prime;
+ else {
+ denominator.push_back(denom);
+ denom=1;
+ denom*=prime;
+ //cout<<num<<":"<<denom<<":"<<mul<<endl;
+ }
+ }
+
+
+ }
+ numerator.push_back(num);
+ denominator.push_back(denom);
+ h_x=1;
+ int d=0;
+ for(int n=0;n<numerator.size();) {
+ if(isfinite(h_x*numerator[n])) {
+ h_x*=numerator[n];
+ n++;
+ }
+ else if(d<denominator.size()){
+ h_x/=denominator[d];
+ d++;
+ }
+ else
+ return -1;
+ //cout<<h_x<<endl;
+ }
+
+ for(;d<denominator.size();d++) {
+ if((boost::math::isfinite)(h_x/denominator[d])) {
+ h_x/=denominator[d];
+ }
+ else
+ return -10;
+ //cout<<h_x<<endl;
+ }
+ return h_x;
+
+ }
+ }
+ else {
+ //calculate h(0;r,n,N) or h(r-N+n;r,n,N) depending on r-N+n
+ RealType m,factorial1,factorial2,factorial3,factorial4;
+
+ bool tail_recurrence=((min(r,n)-x)<(x-std::max(r-N+n,0)));
+ if(tail_recurrence && dist.m_tail_recurrence) {
+
+ RealType t=min(r,n);
+ factorial1=n;factorial2=N-t;factorial3=N;factorial4=n-t;
+ }
+ else if(r-N+n>0) {
+ factorial1=n;factorial2=r;factorial3=N;factorial4=r-N+n;
+ }
+ else {
+ m=N-n;
+ factorial1=m;factorial2=N-r;factorial3=N;factorial4=m-r;
+ }
+ //cout<<factorial1<<":"<<factorial2<<":"<<factorial3<<":"<<factorial4<<endl;
+
+ if(dist.m_gamma) {
+ h_x=std::exp(static_cast<long double>(boost::math::lgamma(factorial1+1))+boost::math::lgamma(factorial2+1)-boost::math::lgamma(factorial3+1)-boost::math::lgamma(factorial4+1));
+ }
+ else {
+ RealType num=1,denom=1;
+ long double mul=1;
+
+ RealType check=std::max(std::max(std::max(factorial1,factorial2),factorial3),factorial4);
+ vector<RealType> numerator;
+ vector<RealType> denominator;
+ for(int index_of_prime=0;index_of_prime<prime_table.size() && prime_table[index_of_prime]<=check;++index_of_prime) {
+
+ RealType exponent=detail::exponent_of_prime(factorial1, prime_table[index_of_prime])
+ + detail::exponent_of_prime(factorial2, prime_table[index_of_prime])
+ - detail::exponent_of_prime(factorial3, prime_table[index_of_prime])
+ - detail::exponent_of_prime(factorial4, prime_table[index_of_prime]);
+
+
+ if(exponent==0)
+ continue;
+ RealType prime=prime_table[index_of_prime];
+
+ //compute numerator and denominator, and check for overflow
+
+ if(exponent>0)
+ for(RealType j=0;j<exponent;j++) {
+ if((num*prime)/prime==num)
+ num*=prime;
+ else {
+ numerator.push_back(num);
+ num=1;
+ num*=prime;
+ //cout<<num<<":"<<denom<<":"<<mul<<endl;
+ }
+ }
+ else
+ for(RealType j=0;j>exponent;j--) {
+ if((denom*prime)/prime==denom)
+ denom*=prime;
+ else {
+ denominator.push_back(denom);
+ denom=1;
+ denom*=prime;
+ //cout<<num<<":"<<denom<<":"<<mul<<endl;
+ }
+ }
+
+
+ }
+ numerator.push_back(num);
+ denominator.push_back(denom);
+ h_x=1;
+ int d=0;
+ for(int n=0;n<numerator.size();) {
+ if(isfinite(h_x*numerator[n])) {
+ h_x*=numerator[n];
+ n++;
+ }
+ else if(d<denominator.size()){
+ h_x/=denominator[d];
+ d++;
+ }
+ else
+ return -1;
+ }
+
+ for(;d<denominator.size();d++)
+ if((boost::math::isfinite)(h_x/denominator[d])) {
+ h_x/=denominator[d];
+ }
+ else
+ return -10;
+ }
+
+ RealType temp=N-n-r;
+
+ if(!dist.m_tail_recurrence || !tail_recurrence) {
+ //iterate to get h(x;r,n,N)
+ for(RealType x_counter=(r-N+n>0?r-N+n:0);x_counter<x;x_counter++) {
+ h_x=h_x*( static_cast<long double>((n-x_counter)*(r-x_counter))/((x_counter+1)*(temp+x_counter+1)) );
+
+ }
+ }
+ else {
+ for(RealType x_counter=std::min(r,n);x_counter>x;x_counter--) {
+ h_x=h_x*( static_cast<long double>((x_counter)*(temp+x_counter))/((n-x_counter+1)*(r-x_counter+1)) );
+
+ }
+ }
+ }
+ return h_x;
+ }
+
+ }
+
+
+}
+
+
+/*
+h(6000;10000,20000,25000)
+
+Without lgamma,Without tail recurrence relation
+4.030999212699588022979939e-917
+0.0001538085937500000010842022
+
+With lgamma,without tail recurrence relation
+4.030999212715254444050664e-917
+2.746582031250000067762636e-05
+
+Without lgamma,With tail recurrence relation
+4.03099921269958800294152e-917
+0.0002221679687500000075894152
+
+With lgamma,with tail recurrence relation
+4.030999212759628086687057e-917
+0.0001025390624999999962052924
+
+Mathematica - 4.03099921269958801406602974963185e-917
+
+
+
+h(600;1000,2000,2500) (At double precision)
+Without lgamma,Without tail recurrence relation
+1.837712217487969618942744e-93
+2.56347656249999990513231e-05
+
+With lgamma,without tail recurrence relation
+1.837712217488751593267362e-93
+5.264282226562499593424185e-06
+
+Without lgamma,With tail recurrence relation
+1.837712217487969618942744e-93
+2.56347656249999990513231e-05
+
+With lgamma,with tail recurrence relation
+1.837712217488751593267362e-93
+5.187988281250000372694497e-06
+
+Mathematica - 1.83771221748796930158735021740153*10^-93
+
+h(8000;10000,20000,25000) (At double precision)
+Without lgamma,Without tail recurrence relation
+0
+0.000244140625
+
+With lgamma,without tail recurrence relation
+0
+7.324218749999999728949457e-05
+
+Without lgamma,With tail recurrence relation
+0
+0.000236816406249999993494787
+
+With lgamma,with tail recurrence relation
+0
+4.760742187500000162630326e-05
+
+With direct computation of h_x (without lgamma)
+0.0128750932195924993467484
+0.0004296875000000000021684043
+
+With direct computation of h_x (with lgamma)
+0.01287509322016390685139431
+6.942749023437500237169225e-06
+
+Mathematica - 0.0128750932195925027035149077241718
+*/
+
+

Next message: emil_at_[hidden]: "[Boost-commit] svn:boost r48543 - trunk/boost/exception"
Previous message: gautamcool88_at_[hidden]: "[Boost-commit] svn:boost r48541 - sandbox/SOC/2008/parrallel_math/libs/math/test"

Date view	Thread view	Subject view	Author view

Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk