Fastest Prime Algorithm

<?php
    // HERE IS EXAMPLE CODE. LETS HACK BY YOURSELF!

    // sqrt(10000000) -> 3162.27 -> 3163 -> 447 primes -> [2,3,5,6,...,3121,3137,3163]
    $primeNums = array(2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997,1009,1013,1019,1021,1031,1033,1039,1049,1051,1061,1063,1069,1087,1091,1093,1097,1103,1109,1117,1123,1129,1151,1153,1163,1171,1181,1187,1193,1201,1213,1217,1223,1229,1231,1237,1249,1259,1277,1279,1283,1289,1291,1297,1301,1303,1307,1319,1321,1327,1361,1367,1373,1381,1399,1409,1423,1427,1429,1433,1439,1447,1451,1453,1459,1471,1481,1483,1487,1489,1493,1499,1511,1523,1531,1543,1549,1553,1559,1567,1571,1579,1583,1597,1601,1607,1609,1613,1619,1621,1627,1637,1657,1663,1667,1669,1693,1697,1699,1709,1721,1723,1733,1741,1747,1753,1759,1777,1783,1787,1789,1801,1811,1823,1831,1847,1861,1867,1871,1873,1877,1879,1889,1901,1907,1913,1931,1933,1949,1951,1973,1979,1987,1993,1997,1999,2003,2011,2017,2027,2029,2039,2053,2063,2069,2081,2083,2087,2089,2099,2111,2113,2129,2131,2137,2141,2143,2153,2161,2179,2203,2207,2213,2221,2237,2239,2243,2251,2267,2269,2273,2281,2287,2293,2297,2309,2311,2333,2339,2341,2347,2351,2357,2371,2377,2381,2383,2389,2393,2399,2411,2417,2423,2437,2441,2447,2459,2467,2473,2477,2503,2521,2531,2539,2543,2549,2551,2557,2579,2591,2593,2609,2617,2621,2633,2647,2657,2659,2663,2671,2677,2683,2687,2689,2693,2699,2707,2711,2713,2719,2729,2731,2741,2749,2753,2767,2777,2789,2791,2797,2801,2803,2819,2833,2837,2843,2851,2857,2861,2879,2887,2897,2903,2909,2917,2927,2939,2953,2957,2963,2969,2971,2999,3001,3011,3019,3023,3037,3041,3049,3061,3067,3079,3083,3089,3109,3119,3121,3137,3163);


    // Total Primes
    $t[0]=0;
    $t[10000]=1229;
    $t[20000]=2262;
    $t[30000]=3245;
    $t[40000]=4203;
    $t[50000]=5133;
    $t[60000]=6057;
    $t[70000]=6935;
    $t[80000]=7837;
    $t[90000]=8713;
    $t[100000]=9592;
    $t[110000]=10453;
    $t[120000]=11301;
    $t[130000]=12159;
    $t[140000]=13010;
    $t[150000]=13848;
    $t[160000]=14683;
    $t[170000]=15497;
    $t[180000]=16342;
    $t[190000]=17170;
    $t[200000]=17984;
    $t[210000]=18807;
    $t[220000]=19618;
    $t[230000]=20437;
    $t[240000]=21221;
    $t[250000]=22044;
    $t[260000]=22837;
    $t[270000]=23642;
    $t[280000]=24432;
    $t[290000]=25224;
    $t[300000]=25997;
    $t[310000]=26800;
    $t[320000]=27608;
    $t[330000]=28404;
    $t[340000]=29182;
    $t[350000]=29977;
    $t[360000]=30757;
    $t[370000]=31522;
    $t[380000]=32300;
    $t[390000]=33067;
    $t[400000]=33860;
    $t[410000]=34614;
    $t[420000]=35390;
    $t[430000]=36162;
    $t[440000]=36941;
    $t[450000]=37706;
    $t[460000]=38458;
    $t[470000]=39223;
    $t[480000]=40005;
    $t[490000]=40766;
    $t[500000]=41538;
    $t[510000]=42291;
    $t[520000]=43061;
    $t[530000]=43825;
    $t[540000]=44572;
    $t[550000]=45322;
    $t[560000]=46072;
    $t[570000]=46819;
    $t[580000]=47588;
    $t[590000]=48351;
    $t[600000]=49098;
    $t[610000]=49861;
    $t[620000]=50612;
    $t[630000]=51341;
    $t[640000]=52074;
    $t[650000]=52831;
    $t[660000]=53564;
    $t[670000]=54309;
    $t[680000]=55063;
    $t[690000]=55815;
    $t[700000]=56543;
    $t[710000]=57306;
    $t[720000]=58029;
    $t[730000]=58789;
    $t[740000]=59531;
    $t[750000]=60238;
    $t[760000]=60978;
    $t[770000]=61733;
    $t[780000]=62468;
    $t[790000]=63206;
    $t[800000]=63951;
    $t[810000]=64683;
    $t[820000]=65416;
    $t[830000]=66161;
    $t[840000]=66890;
    $t[850000]=67617;
    $t[860000]=68342;
    $t[870000]=69095;
    $t[880000]=69823;
    $t[890000]=70555;
    $t[900000]=71274;
    $t[910000]=72026;
    $t[920000]=72734;
    $t[930000]=73474;
    $t[940000]=74187;
    $t[950000]=74907;
    $t[960000]=75618;
    $t[970000]=76350;
    $t[980000]=77067;
    $t[990000]=77777;
    $t[1000000]=78498;
    $t[1010000]=79251;
    $t[1020000]=79970;
    $t[1030000]=80702;
    $t[1040000]=81403;
    $t[1050000]=82134;
    $t[1060000]=82832;
    $t[1070000]=83548;
    $t[1080000]=84270;
    $t[1090000]=84976;
    $t[1100000]=85714;
    $t[1110000]=86450;
    $t[1120000]=87166;
    $t[1130000]=87884;
    $t[1140000]=88602;
    $t[1150000]=89302;
    $t[1160000]=90030;
    $t[1170000]=90764;
    $t[1180000]=91490;
    $t[1190000]=92225;
    $t[1200000]=92938;
    $t[1210000]=93614;
    $t[1220000]=94358;
    $t[1230000]=95051;
    $t[1240000]=95745;
    $t[1250000]=96469;
    $t[1260000]=97182;
    $t[1270000]=97900;
    $t[1280000]=98610;
    $t[1290000]=99332;
    $t[1300000]=100021;
    $t[1310000]=100730;
    $t[1320000]=101433;
    $t[1330000]=102146;
    $t[1340000]=102852;
    $t[1350000]=103544;
    $t[1360000]=104258;
    $t[1370000]=104967;
    $t[1380000]=105690;
    $t[1390000]=106385;
    $t[1400000]=107126;
    $t[1410000]=107805;
    $t[1420000]=108487;
    $t[1430000]=109205;
    $t[1440000]=109928;
    $t[1450000]=110630;
    $t[1460000]=111331;
    $t[1470000]=112047;
    $t[1480000]=112752;
    $t[1490000]=113458;
    $t[1500000]=114155;
    $t[1510000]=114886;
    $t[1520000]=115588;
    $t[1530000]=116279;
    $t[1540000]=116965;
    $t[1550000]=117663;
    $t[1560000]=118376;
    $t[1570000]=119057;
    $t[1580000]=119758;
    $t[1590000]=120451;
    $t[1600000]=121127;
    $t[1610000]=121846;
    $t[1620000]=122540;
    $t[1630000]=123250;
    $t[1640000]=123942;
    $t[1650000]=124634;
    $t[1660000]=125335;
    $t[1670000]=126051;
    $t[1680000]=126753;
    $t[1690000]=127428;
    $t[1700000]=128141;
    $t[1710000]=128837;
    $t[1720000]=129522;
    $t[1730000]=130213;
    $t[1740000]=130902;
    $t[1750000]=131608;
    $t[1760000]=132292;
    $t[1770000]=132971;
    $t[1780000]=133671;
    $t[1790000]=134359;
    $t[1800000]=135072;
    $t[1810000]=135776;
    $t[1820000]=136448;
    $t[1830000]=137166;
    $t[1840000]=137841;
    $t[1850000]=138542;
    $t[1860000]=139249;
    $t[1870000]=139952;
    $t[1880000]=140641;
    $t[1890000]=141338;
    $t[1900000]=142029;
    $t[1910000]=142718;
    $t[1920000]=143414;
    $t[1930000]=144125;
    $t[1940000]=144810;
    $t[1950000]=145502;
    $t[1960000]=146186;
    $t[1970000]=146859;
    $t[1980000]=147529;
    $t[1990000]=148219;
    $t[2000000]=148933;
    $t[2010000]=149638;
    $t[2020000]=150328;
    $t[2030000]=151021;
    $t[2040000]=151711;
    $t[2050000]=152382;
    $t[2060000]=153078;
    $t[2070000]=153772;
    $t[2080000]=154445;
    $t[2090000]=155131;
    $t[2100000]=155805;
    $t[2110000]=156504;
    $t[2120000]=157187;
    $t[2130000]=157884;
    $t[2140000]=158557;
    $t[2150000]=159250;
    $t[2160000]=159962;
    $t[2170000]=160629;
    $t[2180000]=161319;
    $t[2190000]=161998;
    $t[2200000]=162662;
    $t[2210000]=163363;
    $t[2220000]=164023;
    $t[2230000]=164718;
    $t[2240000]=165398;
    $t[2250000]=166081;
    $t[2260000]=166769;
    $t[2270000]=167470;
    $t[2280000]=168164;
    $t[2290000]=168826;
    $t[2300000]=169511;
    $t[2310000]=170201;
    $t[2320000]=170863;
    $t[2330000]=171535;
    $t[2340000]=172206;
    $t[2350000]=172873;
    $t[2360000]=173563;
    $t[2370000]=174254;
    $t[2380000]=174916;
    $t[2390000]=175621;
    $t[2400000]=176302;
    $t[2410000]=176962;
    $t[2420000]=177654;
    $t[2430000]=178326;
    $t[2440000]=178983;
    $t[2450000]=179684;
    $t[2460000]=180371;
    $t[2470000]=181039;
    $t[2480000]=181711;
    $t[2490000]=182398;
    $t[2500000]=183072;
    $t[2510000]=183748;
    $t[2520000]=184423;
    $t[2530000]=185120;
    $t[2540000]=185792;
    $t[2550000]=186462;
    $t[2560000]=187134;
    $t[2570000]=187812;
    $t[2580000]=188511;
    $t[2590000]=189204;
    $t[2600000]=189880;
    $t[2610000]=190533;
    $t[2620000]=191214;
    $t[2630000]=191886;
    $t[2640000]=192567;
    $t[2650000]=193256;
    $t[2660000]=193951;
    $t[2670000]=194613;
    $t[2680000]=195278;
    $t[2690000]=195959;
    $t[2700000]=196645;
    $t[2710000]=197324;
    $t[2720000]=198019;
    $t[2730000]=198664;
    $t[2740000]=199321;
    $t[2750000]=199993;
    $t[2760000]=200664;
    $t[2770000]=201349;
    $t[2780000]=202015;
    $t[2790000]=202678;
    $t[2800000]=203362;
    $t[2810000]=204052;
    $t[2820000]=204747;
    $t[2830000]=205414;
    $t[2840000]=206118;
    $t[2850000]=206789;
    $t[2860000]=207443;
    $t[2870000]=208116;
    $t[2880000]=208769;
    $t[2890000]=209447;
    $t[2900000]=210109;
    $t[2910000]=210790;
    $t[2920000]=211453;
    $t[2930000]=212124;
    $t[2940000]=212804;
    $t[2950000]=213453;
    $t[2960000]=214105;
    $t[2970000]=214799;
    $t[2980000]=215458;
    $t[2990000]=216129;
    $t[3000000]=216816;
    $t[3010000]=217486;
    $t[3020000]=218145;
    $t[3030000]=218808;
    $t[3040000]=219465;
    $t[3050000]=220136;
    $t[3060000]=220793;
    $t[3070000]=221457;
    $t[3080000]=222152;
    $t[3090000]=222838;
    $t[3100000]=223492;
    $t[3110000]=224168;
    $t[3120000]=224845;
    $t[3130000]=225511;
    $t[3140000]=226177;
    $t[3150000]=226835;
    $t[3160000]=227512;
    $t[3170000]=228180;
    $t[3180000]=228843;
    $t[3190000]=229534;
    $t[3200000]=230209;
    $t[3210000]=230895;
    $t[3220000]=231569;
    $t[3230000]=232241;
    $t[3240000]=232928;
    $t[3250000]=233577;
    $t[3260000]=234239;
    $t[3270000]=234916;
    $t[3280000]=235582;
    $t[3290000]=236252;
    $t[3300000]=236900;
    $t[3310000]=237573;
    $t[3320000]=238233;
    $t[3330000]=238910;
    $t[3340000]=239555;
    $t[3350000]=240230;
    $t[3360000]=240853;
    $t[3370000]=241541;
    $t[3380000]=242208;
    $t[3390000]=242877;
    $t[3400000]=243539;
    $t[3410000]=244216;
    $t[3420000]=244882;
    $t[3430000]=245554;
    $t[3440000]=246239;
    $t[3450000]=246909;
    $t[3460000]=247555;
    $t[3470000]=248209;
    $t[3480000]=248846;
    $t[3490000]=249482;
    $t[3500000]=250150;
    $t[3510000]=250801;
    $t[3520000]=251464;
    $t[3530000]=252094;
    $t[3540000]=252757;
    $t[3550000]=253412;
    $t[3560000]=254080;
    $t[3570000]=254750;
    $t[3580000]=255390;
    $t[3590000]=256057;
    $t[3600000]=256726;
    $t[3610000]=257418;
    $t[3620000]=258088;
    $t[3630000]=258774;
    $t[3640000]=259426;
    $t[3650000]=260064;
    $t[3660000]=260714;
    $t[3670000]=261376;
    $t[3680000]=262078;
    $t[3690000]=262716;
    $t[3700000]=263397;
    $t[3710000]=264052;
    $t[3720000]=264723;
    $t[3730000]=265410;
    $t[3740000]=266068;
    $t[3750000]=266717;
    $t[3760000]=267384;
    $t[3770000]=268016;
    $t[3780000]=268671;
    $t[3790000]=269330;
    $t[3800000]=269987;
    $t[3810000]=270643;
    $t[3820000]=271325;
    $t[3830000]=271999;
    $t[3840000]=272645;
    $t[3850000]=273322;
    $t[3860000]=273972;
    $t[3870000]=274618;
    $t[3880000]=275269;
    $t[3890000]=275930;
    $t[3900000]=276611;
    $t[3910000]=277262;
    $t[3920000]=277920;
    $t[3930000]=278595;
    $t[3940000]=279243;
    $t[3950000]=279921;
    $t[3960000]=280564;
    $t[3970000]=281202;
    $t[3980000]=281870;
    $t[3990000]=282504;
    $t[4000000]=283146;
    $t[4010000]=283806;
    $t[4020000]=284464;
    $t[4030000]=285132;
    $t[4040000]=285809;
    $t[4050000]=286490;
    $t[4060000]=287133;
    $t[4070000]=287786;
    $t[4080000]=288456;
    $t[4090000]=289109;
    $t[4100000]=289774;
    $t[4110000]=290437;
    $t[4120000]=291065;
    $t[4130000]=291717;
    $t[4140000]=292349;
    $t[4150000]=293010;
    $t[4160000]=293672;
    $t[4170000]=294343;
    $t[4180000]=294994;
    $t[4190000]=295667;
    $t[4200000]=296314;
    $t[4210000]=296984;
    $t[4220000]=297628;
    $t[4230000]=298291;
    $t[4240000]=298919;
    $t[4250000]=299583;
    $t[4260000]=300243;
    $t[4270000]=300887;
    $t[4280000]=301543;
    $t[4290000]=302175;
    $t[4300000]=302824;
    $t[4310000]=303486;
    $t[4320000]=304152;
    $t[4330000]=304793;
    $t[4340000]=305449;
    $t[4350000]=306084;
    $t[4360000]=306724;
    $t[4370000]=307377;
    $t[4380000]=308038;
    $t[4390000]=308700;
    $t[4400000]=309335;
    $t[4410000]=309976;
    $t[4420000]=310655;
    $t[4430000]=311338;
    $t[4440000]=311994;
    $t[4450000]=312666;
    $t[4460000]=313321;
    $t[4470000]=313981;
    $t[4480000]=314627;
    $t[4490000]=315310;
    $t[4500000]=315948;
    $t[4510000]=316601;
    $t[4520000]=317239;
    $t[4530000]=317885;
    $t[4540000]=318516;
    $t[4550000]=319164;
    $t[4560000]=319823;
    $t[4570000]=320496;
    $t[4580000]=321146;
    $t[4590000]=321786;
    $t[4600000]=322441;
    $t[4610000]=323103;
    $t[4620000]=323759;
    $t[4630000]=324404;
    $t[4640000]=325055;
    $t[4650000]=325706;
    $t[4660000]=326322;
    $t[4670000]=326987;
    $t[4680000]=327653;
    $t[4690000]=328320;
    $t[4700000]=328964;
    $t[4710000]=329616;
    $t[4720000]=330269;
    $t[4730000]=330912;
    $t[4740000]=331575;
    $t[4750000]=332219;
    $t[4760000]=332861;
    $t[4770000]=333516;
    $t[4780000]=334144;
    $t[4790000]=334801;
    $t[4800000]=335439;
    $t[4810000]=336096;
    $t[4820000]=336751;
    $t[4830000]=337382;
    $t[4840000]=338060;
    $t[4850000]=338694;
    $t[4860000]=339339;
    $t[4870000]=340008;
    $t[4880000]=340644;
    $t[4890000]=341313;
    $t[4900000]=341992;
    $t[4910000]=342643;
    $t[4920000]=343277;
    $t[4930000]=343930;
    $t[4940000]=344585;
    $t[4950000]=345235;
    $t[4960000]=345875;
    $t[4970000]=346558;
    $t[4980000]=347219;
    $t[4990000]=347872;
    $t[5000000]=348513;
    $t[5010000]=349152;
    $t[5020000]=349791;
    $t[5030000]=350449;
    $t[5040000]=351087;
    $t[5050000]=351715;
    $t[5060000]=352383;
    $t[5070000]=353022;
    $t[5080000]=353670;
    $t[5090000]=354325;
    $t[5100000]=354971;
    $t[5110000]=355603;
    $t[5120000]=356244;
    $t[5130000]=356899;
    $t[5140000]=357559;
    $t[5150000]=358198;
    $t[5160000]=358842;
    $t[5170000]=359487;
    $t[5180000]=360118;
    $t[5190000]=360759;
    $t[5200000]=361407;
    $t[5210000]=362066;
    $t[5220000]=362715;
    $t[5230000]=363365;
    $t[5240000]=364012;
    $t[5250000]=364685;
    $t[5260000]=365315;
    $t[5270000]=365964;
    $t[5280000]=366617;
    $t[5290000]=367246;
    $t[5300000]=367900;
    $t[5310000]=368554;
    $t[5320000]=369191;
    $t[5330000]=369834;
    $t[5340000]=370483;
    $t[5350000]=371131;
    $t[5360000]=371773;
    $t[5370000]=372415;
    $t[5380000]=373068;
    $t[5390000]=373722;
    $t[5400000]=374362;
    $t[5410000]=374992;
    $t[5420000]=375632;
    $t[5430000]=376289;
    $t[5440000]=376939;
    $t[5450000]=377574;
    $t[5460000]=378233;
    $t[5470000]=378874;
    $t[5480000]=379497;
    $t[5490000]=380148;
    $t[5500000]=380800;
    $t[5510000]=381438;
    $t[5520000]=382061;
    $t[5530000]=382694;
    $t[5540000]=383361;
    $t[5550000]=383979;
    $t[5560000]=384613;
    $t[5570000]=385268;
    $t[5580000]=385904;
    $t[5590000]=386545;
    $t[5600000]=387202;
    $t[5610000]=387835;
    $t[5620000]=388473;
    $t[5630000]=389111;
    $t[5640000]=389754;
    $t[5650000]=390378;
    $t[5660000]=391019;
    $t[5670000]=391654;
    $t[5680000]=392292;
    $t[5690000]=392927;
    $t[5700000]=393606;
    $t[5710000]=394241;
    $t[5720000]=394908;
    $t[5730000]=395540;
    $t[5740000]=396172;
    $t[5750000]=396826;
    $t[5760000]=397462;
    $t[5770000]=398079;
    $t[5780000]=398716;
    $t[5790000]=399353;
    $t[5800000]=399993;
    $t[5810000]=400647;
    $t[5820000]=401279;
    $t[5830000]=401906;
    $t[5840000]=402547;
    $t[5850000]=403204;
    $t[5860000]=403831;
    $t[5870000]=404466;
    $t[5880000]=405107;
    $t[5890000]=405784;
    $t[5900000]=406429;
    $t[5910000]=407077;
    $t[5920000]=407744;
    $t[5930000]=408393;
    $t[5940000]=409039;
    $t[5950000]=409672;
    $t[5960000]=410311;
    $t[5970000]=410944;
    $t[5980000]=411580;
    $t[5990000]=412224;
    $t[6000000]=412849;
    $t[6010000]=413510;
    $t[6020000]=414148;
    $t[6030000]=414812;
    $t[6040000]=415413;
    $t[6050000]=416040;
    $t[6060000]=416706;
    $t[6070000]=417321;
    $t[6080000]=417974;
    $t[6090000]=418602;
    $t[6100000]=419246;
    $t[6110000]=419898;
    $t[6120000]=420539;
    $t[6130000]=421175;
    $t[6140000]=421812;
    $t[6150000]=422449;
    $t[6160000]=423094;
    $t[6170000]=423752;
    $t[6180000]=424379;
    $t[6190000]=424998;
    $t[6200000]=425648;
    $t[6210000]=426292;
    $t[6220000]=426894;
    $t[6230000]=427547;
    $t[6240000]=428179;
    $t[6250000]=428816;
    $t[6260000]=429466;
    $t[6270000]=430113;
    $t[6280000]=430749;
    $t[6290000]=431413;
    $t[6300000]=432073;
    $t[6310000]=432719;
    $t[6320000]=433353;
    $t[6330000]=434002;
    $t[6340000]=434635;
    $t[6350000]=435265;
    $t[6360000]=435902;
    $t[6370000]=436528;
    $t[6380000]=437137;
    $t[6390000]=437765;
    $t[6400000]=438410;
    $t[6410000]=439040;
    $t[6420000]=439683;
    $t[6430000]=440318;
    $t[6440000]=440929;
    $t[6450000]=441562;
    $t[6460000]=442221;
    $t[6470000]=442853;
    $t[6480000]=443481;
    $t[6490000]=444118;
    $t[6500000]=444757;
    $t[6510000]=445399;
    $t[6520000]=446039;
    $t[6530000]=446685;
    $t[6540000]=447314;
    $t[6550000]=447955;
    $t[6560000]=448595;
    $t[6570000]=449229;
    $t[6580000]=449868;
    $t[6590000]=450527;
    $t[6600000]=451159;
    $t[6610000]=451800;
    $t[6620000]=452462;
    $t[6630000]=453077;
    $t[6640000]=453697;
    $t[6650000]=454337;
    $t[6660000]=454950;
    $t[6670000]=455598;
    $t[6680000]=456228;
    $t[6690000]=456846;
    $t[6700000]=457497;
    $t[6710000]=458152;
    $t[6720000]=458786;
    $t[6730000]=459432;
    $t[6740000]=460066;
    $t[6750000]=460707;
    $t[6760000]=461368;
    $t[6770000]=461987;
    $t[6780000]=462619;
    $t[6790000]=463239;
    $t[6800000]=463872;
    $t[6810000]=464504;
    $t[6820000]=465157;
    $t[6830000]=465791;
    $t[6840000]=466422;
    $t[6850000]=467055;
    $t[6860000]=467718;
    $t[6870000]=468378;
    $t[6880000]=469001;
    $t[6890000]=469652;
    $t[6900000]=470283;
    $t[6910000]=470920;
    $t[6920000]=471561;
    $t[6930000]=472176;
    $t[6940000]=472828;
    $t[6950000]=473470;
    $t[6960000]=474101;
    $t[6970000]=474749;
    $t[6980000]=475381;
    $t[6990000]=476011;
    $t[7000000]=476648;
    $t[7010000]=477277;
    $t[7020000]=477907;
    $t[7030000]=478560;
    $t[7040000]=479208;
    $t[7050000]=479864;
    $t[7060000]=480492;
    $t[7070000]=481086;
    $t[7080000]=481746;
    $t[7090000]=482386;
    $t[7100000]=483015;
    $t[7110000]=483678;
    $t[7120000]=484286;
    $t[7130000]=484897;
    $t[7140000]=485514;
    $t[7150000]=486167;
    $t[7160000]=486807;
    $t[7170000]=487436;
    $t[7180000]=488051;
    $t[7190000]=488681;
    $t[7200000]=489319;
    $t[7210000]=489951;
    $t[7220000]=490581;
    $t[7230000]=491216;
    $t[7240000]=491841;
    $t[7250000]=492494;
    $t[7260000]=493109;
    $t[7270000]=493756;
    $t[7280000]=494398;
    $t[7290000]=495034;
    $t[7300000]=495666;
    $t[7310000]=496294;
    $t[7320000]=496924;
    $t[7330000]=497560;
    $t[7340000]=498176;
    $t[7350000]=498797;
    $t[7360000]=499439;
    $t[7370000]=500082;
    $t[7380000]=500717;
    $t[7390000]=501343;
    $t[7400000]=501962;
    $t[7410000]=502582;
    $t[7420000]=503223;
    $t[7430000]=503856;
    $t[7440000]=504491;
    $t[7450000]=505147;
    $t[7460000]=505762;
    $t[7470000]=506372;
    $t[7480000]=507019;
    $t[7490000]=507650;
    $t[7500000]=508261;
    $t[7510000]=508887;
    $t[7520000]=509513;
    $t[7530000]=510126;
    $t[7540000]=510764;
    $t[7550000]=511417;
    $t[7560000]=512062;
    $t[7570000]=512677;
    $t[7580000]=513284;
    $t[7590000]=513921;
    $t[7600000]=514565;
    $t[7610000]=515222;
    $t[7620000]=515838;
    $t[7630000]=516487;
    $t[7640000]=517098;
    $t[7650000]=517740;
    $t[7660000]=518372;
    $t[7670000]=518998;
    $t[7680000]=519628;
    $t[7690000]=520267;
    $t[7700000]=520910;
    $t[7710000]=521522;
    $t[7720000]=522167;
    $t[7730000]=522797;
    $t[7740000]=523403;
    $t[7750000]=524026;
    $t[7760000]=524652;
    $t[7770000]=525264;
    $t[7780000]=525911;
    $t[7790000]=526522;
    $t[7800000]=527154;
    $t[7810000]=527791;
    $t[7820000]=528423;
    $t[7830000]=529046;
    $t[7840000]=529688;
    $t[7850000]=530334;
    $t[7860000]=530964;
    $t[7870000]=531592;
    $t[7880000]=532239;
    $t[7890000]=532880;
    $t[7900000]=533506;
    $t[7910000]=534136;
    $t[7920000]=534752;
    $t[7930000]=535385;
    $t[7940000]=536013;
    $t[7950000]=536652;
    $t[7960000]=537256;
    $t[7970000]=537890;
    $t[7980000]=538528;
    $t[7990000]=539162;
    $t[8000000]=539777;
    $t[8010000]=540414;
    $t[8020000]=541023;
    $t[8030000]=541654;
    $t[8040000]=542259;
    $t[8050000]=542898;
    $t[8060000]=543549;
    $t[8070000]=544176;
    $t[8080000]=544799;
    $t[8090000]=545417;
    $t[8100000]=546024;
    $t[8110000]=546643;
    $t[8120000]=547276;
    $t[8130000]=547927;
    $t[8140000]=548528;
    $t[8150000]=549150;
    $t[8160000]=549798;
    $t[8170000]=550429;
    $t[8180000]=551053;
    $t[8190000]=551701;
    $t[8200000]=552319;
    $t[8210000]=552957;
    $t[8220000]=553587;
    $t[8230000]=554210;
    $t[8240000]=554848;
    $t[8250000]=555479;
    $t[8260000]=556097;
    $t[8270000]=556716;
    $t[8280000]=557344;
    $t[8290000]=557976;
    $t[8300000]=558597;
    $t[8310000]=559228;
    $t[8320000]=559874;
    $t[8330000]=560491;
    $t[8340000]=561109;
    $t[8350000]=561766;
    $t[8360000]=562392;
    $t[8370000]=563000;
    $t[8380000]=563623;
    $t[8390000]=564258;
    $t[8400000]=564877;
    $t[8410000]=565494;
    $t[8420000]=566136;
    $t[8430000]=566746;
    $t[8440000]=567365;
    $t[8450000]=567967;
    $t[8460000]=568606;
    $t[8470000]=569218;
    $t[8480000]=569852;
    $t[8490000]=570491;
    $t[8500000]=571119;
    $t[8510000]=571759;
    $t[8520000]=572390;
    $t[8530000]=573028;
    $t[8540000]=573653;
    $t[8550000]=574274;
    $t[8560000]=574917;
    $t[8570000]=575537;
    $t[8580000]=576191;
    $t[8590000]=576815;
    $t[8600000]=577439;
    $t[8610000]=578081;
    $t[8620000]=578707;
    $t[8630000]=579329;
    $t[8640000]=579964;
    $t[8650000]=580566;
    $t[8660000]=581216;
    $t[8670000]=581845;
    $t[8680000]=582436;
    $t[8690000]=583086;
    $t[8700000]=583714;
    $t[8710000]=584337;
    $t[8720000]=584984;
    $t[8730000]=585613;
    $t[8740000]=586237;
    $t[8750000]=586850;
    $t[8760000]=587486;
    $t[8770000]=588139;
    $t[8780000]=588739;
    $t[8790000]=589397;
    $t[8800000]=590006;
    $t[8810000]=590626;
    $t[8820000]=591236;
    $t[8830000]=591879;
    $t[8840000]=592485;
    $t[8850000]=593112;
    $t[8860000]=593719;
    $t[8870000]=594333;
    $t[8880000]=594973;
    $t[8890000]=595588;
    $t[8900000]=596222;
    $t[8910000]=596829;
    $t[8920000]=597475;
    $t[8930000]=598114;
    $t[8940000]=598741;
    $t[8950000]=599355;
    $t[8960000]=599970;
    $t[8970000]=600583;
    $t[8980000]=601203;
    $t[8990000]=601855;
    $t[9000000]=602489;
    $t[9010000]=603072;
    $t[9020000]=603688;
    $t[9030000]=604301;
    $t[9040000]=604919;
    $t[9050000]=605556;
    $t[9060000]=606160;
    $t[9070000]=606790;
    $t[9080000]=607402;
    $t[9090000]=608058;
    $t[9100000]=608672;
    $t[9110000]=609299;
    $t[9120000]=609906;
    $t[9130000]=610515;
    $t[9140000]=611160;
    $t[9150000]=611788;
    $t[9160000]=612395;
    $t[9170000]=613025;
    $t[9180000]=613663;
    $t[9190000]=614290;
    $t[9200000]=614917;
    $t[9210000]=615525;
    $t[9220000]=616162;
    $t[9230000]=616807;
    $t[9240000]=617434;
    $t[9250000]=618057;
    $t[9260000]=618692;
    $t[9270000]=619303;
    $t[9280000]=619929;
    $t[9290000]=620542;
    $t[9300000]=621177;
    $t[9310000]=621798;
    $t[9320000]=622416;
    $t[9330000]=623036;
    $t[9340000]=623664;
    $t[9350000]=624298;
    $t[9360000]=624926;
    $t[9370000]=625553;
    $t[9380000]=626159;
    $t[9390000]=626788;
    $t[9400000]=627400;
    $t[9410000]=628010;
    $t[9420000]=628643;
    $t[9430000]=629249;
    $t[9440000]=629858;
    $t[9450000]=630495;
    $t[9460000]=631091;
    $t[9470000]=631722;
    $t[9480000]=632341;
    $t[9490000]=632966;
    $t[9500000]=633578;
    $t[9510000]=634216;
    $t[9520000]=634827;
    $t[9530000]=635441;
    $t[9540000]=636072;
    $t[9550000]=636697;
    $t[9560000]=637333;
    $t[9570000]=637939;
    $t[9580000]=638572;
    $t[9590000]=639231;
    $t[9600000]=639851;
    $t[9610000]=640461;
    $t[9620000]=641085;
    $t[9630000]=641712;
    $t[9640000]=642321;
    $t[9650000]=642962;
    $t[9660000]=643576;
    $t[9670000]=644218;
    $t[9680000]=644835;
    $t[9690000]=645451;
    $t[9700000]=646054;
    $t[9710000]=646676;
    $t[9720000]=647275;
    $t[9730000]=647920;
    $t[9740000]=648548;
    $t[9750000]=649175;
    $t[9760000]=649793;
    $t[9770000]=650392;
    $t[9780000]=651005;
    $t[9790000]=651624;
    $t[9800000]=652265;
    $t[9810000]=652890;
    $t[9820000]=653519;
    $t[9830000]=654142;
    $t[9840000]=654751;
    $t[9850000]=655355;
    $t[9860000]=655972;
    $t[9870000]=656592;
    $t[9880000]=657202;
    $t[9890000]=657821;
    $t[9900000]=658445;
    $t[9910000]=659055;
    $t[9920000]=659669;
    $t[9930000]=660285;
    $t[9940000]=660916;
    $t[9950000]=661520;
    $t[9960000]=662138;
    $t[9970000]=662760;
    $t[9980000]=663368;
    $t[9990000]=663965;
    $t[10000000]=664579;




    $n = $argv[1];

    if ( isset($t[$n]) ){
        exit("".$t[$n].PHP_EOL);
    }

    $n2=9990000;
    while ( $n2 > $n ){$n2-=10000;}
    $answer1 = $t[$n2];
    $sqrtN = ($n<0)? 0:(int)sqrt($n);
    $nonPrime = array();
    $i=1;
    $prime = $primeNums[$i];
    while( $prime <= $sqrtN)
    {
        $j = $prime*((int)($n2/$prime));
        if ( $j == 0 ){ // if $n is under 10000 -> $n2 = 0
            $j=$prime*$prime;
        }else{
            $j+= $prime;
            if ( $j%2 == 0 ){
                $j+= $prime;
            }
        }
        // mark all the non-primes
        while( $j <= $n){
            $nonPrime[$j] = 0;
            $j += 2*$prime;
        }
        $i++;
        $prime = $primeNums[$i];
    }
    $n3 = $n - $n2;
    if ( $n3%2 == 0){
        $answer2 = $n3 - $n3/2 - count($nonPrime);
    }else{
        $answer2 = $n3 - ($n3-1)/2 - count($nonPrime);
    }
    $answer = $answer1 + $answer2;
    if( $n < 2 ) $answer=0;



    // DO NOT CHANGE BELOW THIS LINE
    echo $answer.PHP_EOL;