We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #7: 10001st prime
  4. Discussions

Project Euler #7: 10001st prime

  • somnisoft
     + 0 comments

    C solution using precomputed bit array prime table.

    /// Project Euler #7: 10001st prime
/// HackerRank
#include <stdint.h>
#include <stdio.h>

/// HackerRank has a 50 kb source file size limit.
/// Store the list of primes from 3 <= N <= 10^4 in a bit array to save space.
/// Do not include 2 as a prime in the table since it's even. Instead each bit will correspond
/// to an odd number starting at 3. If bit set to 1 means it's prime and 0 means not prime.
static const uint64_t g_prime_bits[] = {
0x40b6894d325a65b7,0x90cb4106c3252619,0x5244b0902d021a64,0x2514416894c308a2,0x841a4c9099212018,
0x8a45244221128325,0x5a05a0436182102,0x3282449409288450,0xc009224b4026184c,0x60108264a0892110,
0x84022480004c1699,0x110412d841344b40,0x4802132ca05144a4,0x348049221821a003,0x92086d204044108,
0x430916912006030,0x886980c10d8242,0xa48b01160225001,0x4904a6902532006,0x265108040029104a,
0xd24584082880c100,0x1a60840a2184d12,0x1042248440291281,0x1208a0510c001928,0x520d00080c20094,
0x949300041b002289,0x880802406030c141,0x6106132c24110036,0x22902c101244a408,0x86012810c801244,
0x40141965008a0434,0x3048098013258200,0x190800806812c041,0x2184000890c32186,0x8049480608240212,
0x1244048300169021,0x2980410484996020,0x200040a0cb400440,0x902c244b04240824,0x49304a0110406194,
0x2d0082211409000,0x502102480c820,0x60164009a41a4492,0x4000422920014c1,0x268024229021b4c,
0xc32994122484500,0x1401200081050048,0x4308821849025220,0x6484022916002104,0x22124c8489243042,
0x8800108a01801200,0x2020104402990d00,0x301800a042618483,0x5101064808b4010c,0x41120a4494c30002,
0x4400c8240042081,0x8100025221340908,0x900800806030830,0x32892110ca019008,0x8a00940205064a0c,
0xa0006820520514,0xa441201690208248,0x1204009808001060,0x4114810012422c82,0x240b40a4012c3080,
0x5065000308908008,0x2100584882000120,0x128a240483408602,0x4305005008929049,0x422900024016086,
0x110982034c0019,0x941220a40a40241,0x68144021a0080c12,0x96006c3212409002,0x8100005120840904,
0xc00886020906520,0x904a0910520c0252,0x240221901205041,0x4530432006000c00,0x41008289443200,
0x8204b0886080d125,0x4205a00b0004400,0x24a200440018083,0x8129060140149045,0x132424000422100,
0x1091202218002419,0x1068025061840100,0x29140020200b0c20,0x84080c008a410448,0x4049905005204104,
0x82802910006004,0x800041060308a008,0x484014004d224825,0x14012184832502,0xa24004b2800c009a,
0x8a2430c101120001,0x28841a0014090020,0x3042449448090282,0x4124a01308248809,0x4420120500884880,
0x1651280002082608,0x92800d805244820,0x4914500482520004,0xa090011088218001,0x8029060204001940,
0x4080810810422490,0xb4c2008091202408,0x44220164009860,0x30896016810086,0x840900a018600050,
0x4200a04a40001005,0x580420800190020,0x20c2451483008012,0xc001a64a04040840,0x28101020a04b2000,
0x1052202051449291,0x825109000944301,0x21128220040a0004,0x9080490208219081,0xc20184910c265008,
0x921141020844a0,0x48060844204040a,0x1b4000014520d821,0x100004892502482,0x84030400814920ca,
0x4044940b68008004,0x28064800b4000030,0x2098212040200090,0x24a00340929000,0xc10500024890084,
0x1412080053008298,0x944001064100100,0x2100930100494806,0x8121120200248b,0x804400d064044,
0x8b48044224a0130,0x42099250090418,0x1800140860328041,0x6400830880900182,0x8641080410610040,
0xd800200329060109,0x802434c00882030,0x20c020b00a490442,0x9020a0114082080d,0x8301a0420802914,
0x442002008009400,0x129020224104821,0x6c10002100400,0xa010240288012041,0x6012030080004c,
0x422080910824134,0x848b681053200002,0x4904861001209264,0x2184802000000920,0x80120880814c1042,
0x1820844801801221,0x804414026102c12,0x100804a083409292,0x922500084022080c,0x60001840144a0086,
0x480010642083001,0x106102080400c101,0x880000c020304b4,0x601411088058448,0x8120801300045b08,
0x4012100d10922500,0x8001201680012200,0x5348100008104a45,0xb0c308960009a0,0x24184082010820c0,
0x84510c028141024,0x2124080804880402,0x290603049410650,0xc104020000a01069,0x2420c02400014116,
0x42018202488008,0x1160320000340261,0x48804304a2190420,0x1200243200009401,0xc329108021804808,
0x44041020104845a0,0xb04201001009a202,0x804001820124840,0x2190020800810404,0x264000b40948205a,
0x82024896004000c,0x8261244a0800d12,0x2090250488290200,0x308040a08b49124,0x2000080014424012,
0x1403240413040088,0x1005024221008a00,0x912410004410080,0x208482050202002,0x840161008201148,
0x4080802c02002194,0x241909004a408,0x5008360000225221,0x64a4404180402422,0x8258080281000000,
0x204204908148209,0xc80100c80114122,0x2080453048408090,0xd101000208228160,0x2100902490882004,
0x21100a20a001618,0x8840108244844901,0x24020a0100082,0x992c3258200489,0xc060848220804804,
0x92004d00480430,0x403410293010409,0x120c001024100004,0x48008800101a4,0x2004c00882500c2,
0x404090006000430c,0x25065a0002980802,0x22100014014894c1,0x5100a04048960060,0x400106184820900,
0x9600000211080601,0x1909000060004308,0x28028120204044a0,0x2689053052413043,0xa0104c009044840,
0x48220045101200a4,0x9688001008202,0x1240909900200205,0x4484020110420c84,0x22410c3401011240,
0xc000940020108021,0x1064008a0104122,0x10102000c8201200,0x1004a0000c941028,0x410402030024004,
0x121208801a04a498,0x149020061208041,0x80500106004012,0x808068108220b003,0x948824209240000,
0xc20890022120004,0x9002290040208613,0x10c241048120004,0x45000a6804d10180,0x200a4c10002512c2,
0x8a2000000002d100,0x480424016102c00,0x20d8010401489010,0x810c000804801804,0x422120000010110,
0x601092259003009,0x9028021064204060,0x2994820582580002,0x1490410018243080,0x821901129800b00,
0x20006902400024,0x4020014c001a251,0x4204941820320260,0x6000490110c02822,0x400411443008,
0x9040804b4182420c,0x2880424422800102,0x4a25a0c3289010,0x402c261008840040,0x402804490030182,
0x4c1002000480291,0x106120d000000028,0x68109320040b0004,0x22010020c8408448,0x24804c305060804,
0x4490180402506400,0x400201611088042,0x100480812400d801,0x2130014000020182,0x800104a208251098,
0x524010c109001200,0xc20504882010810,0x28004b483010002,0x24000000812c,0x64009a0010490180,
0x9040210418042410,0x8109200200b44848,0x880500084090030,0x8600491202241082,0x4b09008000024200,
0x4414114420d000a0,0x8a091240212200,0x84082080d304821,0x120014194830424,0x2008400288403212,
0x100480c221040101,0x9a01808b0002802,0x2290040480408201,0x8104061348308825,0x100020130004890,
0x8442240403040600,0x102d005240000108,0x4800102024400,0x820064100a24840a,0x80900402ca05048,
0x2000032c04000,0x30420190800ca040,0x404030890d120260,0x410092104820104,0x805000809048021a,
0x1a01204948840005,0x2000010cb0884420,0x1082043440601282,0x4200865000021140,0x4510004504002090,
0x441088202442400,0x880020522484c320,0x4006402802510080,0xa0890c00d0412400,0x920020a40200,
0xb40001000a4400,0x8040418411250410,0x1a00000061008244,0x2520810114410002,0x82124004814102c8,
0xa00944049008020,0x2182580826102800,0x22000100824810d2,0x1021000304320024,0x2810002500c90104,
0x8400048211481299,0x190002880090c008,0x60869204044a4404,0x2090c201005a040,0x4160829308201100,
0x420910112180080,0x14096912800d2412,0x100209820020021,0x4484426892100980,0x520c2200290240,
0x1021048848900300,0x2020420014182012,0x2002040482080440,0x400000010c801104,0x2010480090810116,
0x80902c241a000600,0x8048000a40100221,0x1801020000008b6,0x3280250298442008,0x400194420c041208,
0xcb4880020582110,0x8002610240000002,0x4b04129100028000,0x94886800110102,0x220b008208043050,
0x4220244101140108,0x2000024014114810,0x30080194c0001202,0x1028805040800024,0x4902102080806886,
0x8282210049080000,0x9029100840204300,0x6800010524080010,0xa400000240242089,0x821801200021104,
0x416100922000530,0x84032004c2002210,0x94c001040200060,0x6024420010510824,0x414c0409481008,
0x61940001825005,0x20020402082122,0x240019080080280,0x204020008348944,0xc100224a4420102,
0x1008418403201,0x844209004248929,0x6802c300801a0424,0x20812010c2418000,0x28905120244008,
0xc20104800802480,0x440200291012001,0x410082800c100841,0x94c84082002c20,0x5100a011003250,
0x4a4030000006820c,0x906184006884130,0x1090602009000010,0x101a2400820812c,0x6022000414c80982,
0x80c00d0013001080,0x9900100a05100a09,0x4004902120000430,0x3400213040408083,0xc001024021044148,
0x4086004c00020584,0x8049019442242203,0x140860005204000,0x490014814022884,0x650408480003008,
0x104014010004d200,0x20a4082010100,0x90203009088482,0x4305040008a01824,0x68008240b0020000,
0x80100500480c2081,0x865324004008360,0x28104100a4404c82,0x8011481042402448,0x430812100c02000c,
0x22080912006120,0x8309001208040b,0x4008268109004804,0x882180112820,0xa008000051098,
0x8005148860824208,0x2486090090004500,0x300200a400408210,0x225240804060940,0x2822c22014000814,
0x4c000a203083008,0x804800502100c300,0x40040020a0114802,0xa4982c0080600401,0x4001060120800a04,
0x48028804120044a0,0x3089000441052019,0x1208021100108200,0x2010000800820504,0x8009481011440242,
0xa05a00200920329,0x406480806814130,0x124040048a000490,0x1000a20100a00041,0x20880520422006,
0x1010042240048298,0x1000109021a48001,0x1040220045b0080,0x12080420402080c0,0x896004c309021000,
0x44900100020a4090,0x348068804009225a,0x20c000921004020,0x114020110832480,0x4100034086000c2,
0x1240808848840020,0x800434426086902,0x204845000a010640,0x122c00524010900c,0x24209860b0080810,
0x828104a00004a401,0x10c121025104108,0x180020506110806,0x1080010202242403,0x890106000c004240,
0x44a08841028a0000,0x24420090d2200409,0xa00140120300801,0x6100092890502004,0x260944a0180d0080,
0xd000808a00004001,0xa0030c10910c10,0x218012402480040,0x224041244028004,0x4000030112,
0x824105004808b288,0x149021224300261,0x4014830c20404422,0x9088642200000088,0xa0800d025801844,
0x329000204a0100,0x1009409011200651,0x44040008008241,0x20a0402102400880,0x821240161920000a,
0x804190004880000c,0x2020420084902002,0x104820a000089010,0x30c244948200000,0x8121a00a4404084,
0x16830c0210000210,0x9105004800008848,0x80c20880110000,0x91002200441000,0x8008900301205300,
0xc94004502506400,0x489091250290040,0x1200020024009204,0x2024020004420120,0x840a440091053048,
0x4860100069840100,0x504580080000812,0x1000048080400050,0x4201021200128129,0x20500120490812,
0x11008402088411,0x180010c804800a21,0x4804910006000036,0x10601000201408,0x890902c100a00048,
0x4094014030826084,0x94c3080402248012,0x484424980510c020,0x4a0c04094822080,0x2008002008092000,
0x1020108140028124,0x24480030102c00,0x2200002440601440,0x8109000304800140,0x922884184080000,
0x1010002202041600,0x1064028000900860,0x112000804084c02,0x120944308044200b,0x308040021005340,
0x4082102800502024,0x80c00804000c2052,0x940a08841301245,0x2080800186930420,0x8010081011650080,
0x4a2000086012400c,0x2880080034090500,0x2200400040200041,0x4021004a0c148000,0x822902110014880,
0x1000210208089018,0x824001061208828,0x4114000920430802,0x828908201000a043,0x320828308804004,
0x10080c204041b0,0x240b218440080250,0x1844109104128a00,0x2100400100410482,0x210482481642210,
0x4a05340021101021,0x404120804000910,0x12c00010812000c1,0x400804000c020041,0x2800d20000420100,
0x202040051081219,0x880c105021004801,0x4000032004094024,0x80010100422590c0,0x4200009200061108,
0x4482012c00106404,0x1000280280000058,0x1b08948045001825,0x400080002010000,0x8018002090202200,
0x201840b20800105,0x9a4000402180410,0x301a410041210401,0x4008a2404c068120,0x8320040048a0880,
0x80120c8019042400,0x8041304024300208,0x4080800822004014,0x8210610298040008,0x404106430826080c,
0x4894084000882100,0x2400688280080401,0x130430014932c200,0x6084004014c02122,0x440408000280090,
0xc02080802004d120,0x2022104c12092020,0x250410049411012,0x2c801000261828,0x900426030036100,
0x42000050408280,0x8045020004a08320,0x2084c20d004a0000,0x480200050012441,0x4a09105229061000,
0x4060160128200a0,0x2200002248001,0x140241020101200,0x4120082800110984,0x2241089009200012,
0x482120c80112002c,0xc00500004102400,0x208450001081211,0x320240140128040,0x4109a2084c24100,
0x128001240a440080,0x804028801300068,0x4182102484014830,0x1018691040002000,0xa2810520020110c,
0x4022900494,0x200200140000a20b,0x20414980820c820,0x6084090890100822,0x8440040000240058,
0x821900049028324,0x2400410834094012,0x10202008200292,0x4001a65040029008,0x6100900510c00004,
0x9003290402400001,0x10110c004200040,0x6804502484400806,0x9018040052010080,0x8029028020200804,
0x490010c00426100,0x482481040018240,0x140828000220820,0x10436096002084,0x418000488451012,
0x9264048a01864004,0xc80104802900502,0x20a0420814114c1,0x4028001200140840,0x4010884084404880,
0x10c1252018080200,0x25201201008a00,0x6100080004012,0x8498083002608441,0x8909000029004040,
0x404092530000080,0x80002084022c200a,0x4040040144000021,0x6000892004d12004,0x220a042201481008,
0x800100941068104,0x2882100c20900002,0x1b4020800d2,0x9205824b08008820,0x6112400500016080,
0x50002401040200,0x104c20c040a40b20,0x90120822004484,0x80180c00c0200401,0x321140004200840,
0x8308008205a6090,0x80004080c1090258,0x5a08200108029260,0x10402812400d84,0x8000048401602212,
0x8800304a41001121,0x2422000004804020,0xc22110000094d0,0x28820840160825,0x4030102024400804,
0x6422d0003408498,0x1108308000000901,0x20041200a45840a4,0x200090208610001,0xc201801125064800,
0x900812884014,0x30492016000d8010,0x1000841900004200,0x4504004092020100,0x8000080202282,
0x41000b0810d305,0x924484c24002030,0x101a008000080241,0x20800420c028824,0x8020040a0800806,
0x800120844100a081,0x801324000900140,0x6104430100494800,0x3000691000040442,0x8148924204860800,
0x20004402182500,0x9048290081280600,0x1800101809000840,0x4184810004800006,0x8243480208212080,
0x522420c800041020,0x980030084800010,0x40203443010002,0x1304a00900201128,0x402024410032014,
0x8000252618008200,0x9044000000300240,0x4902c00122000030,0x248940008a051080,0x422182c201040b40,
0x22102122080420,0x3000411208013,0x4140840844028200,0x22912002000,0xa0030082084410d0,
0x6020c140104008,0x20a00b0006100130,0x2050040040081281,0x9301260108800109,0x4400986420034006,
0x12800404500c0291,0x1024004a20200801,0x20105840a0c04,0x88000082002042,0x8020800300a04100,
0x14102010000184,0x1001081200640,0x816910000c060,0x1b4ca0100120880,0x408040481092210,
0x5060908028928008,0x2902000080814920,0x8204200a200250,0x109040a04921100,0x6400580024c82102,
0x8861a009011,0x848308205044800,0x4814010122190010,0x10080d1200459482,0x4108165021020048,
0x480000800884404,0x8a00060005a013,0x180404000102d041,0x2010024806010484,0x40488601090000,
0x8220900101025204,0xc80180c00000810,0x2922000484014c3,0x922c000100249100,0x8120005a0084102,
0x44200044b000208,0x1028020044100800,0x9000a0434802,0x80092000ca450082,0x840045001200108,
0x201129301021a0,0x20c1689290202408,0x140841300041,0x6084c14000820c24,0x8610488081211218,
0x4801200168804208,0x2400000890006420,0x1080413008489201,0x1005804b0c200041,0x110400490000894,
0x168009004b4c0400,0x100000220048020,0x180100180100406,0x22810c22c0401001,0x404880800c205140,
0x4800080c000a6100,0x1483010082200210,0x404c920060100064,0x420c16180800120,0x202400018002212,
0xca05100a29001005,0x86020014080800,0x22d0440001209480,0xc121060800841005,0x10424004492804,
0x1452018212088408,0x8120208821140100,0x9129200000100a2,0xa080001218642001,0x8301061009240108,
0x8040121000a0,0x8610403042208,0x800809900028825,0xa4422910410080,0x83200280042,
0x9221900048005201,0x2000094016006110,0x205a212048010050,0x4004204008800040,0x10084020010986,
0x2132c0000400601,0x104300005208240,0x180002c005908b0,0x3090000080400408,0x400014430d820200,
0x4800980102480414,0x409002008008,0x1800209001224001,0x21140308801005a0,0x8042041010491210,
0x802400c120020021,0xc80120000982c00,0x10c061a40b008200,0x20804a04820109,0x4220021b0424094,
0x200082019088400,0x44008a40940300,0x2914400d00084020,0xb008412010041400,0x4a4880900480020c,
0x8000901200a4100,0x2089001010601,0x240a4080c008024,0x420080904500020,0x2104000910c101a,
0x8040004308164221,0x20005200a0080022,0x2402410c1008012,0x1200204940900000,0x6d00880410012084,
0x20d20420c2200,0x814122100024c900,0x6092100802110404,0x101140220800b408,0x328140220804208,
0x4a4006800422010,0x20c108120108a001,0x1008160064301045,0x1308a0816420082,0x2000440088203200,
0x100580802102800c,0x2500014090014512,0x98000000200690,0xc000a41008201028,0x480404080180,
0x2010013443009,0x1800000240800049,0x6084d00022020410,0xa008040010409000,0x8209100120044a48,
0x810080000100504,0x4840801001a003,0x124082092c30d040,0x520830014900c00,0x6084800014c0040,
0x804860801005,0x86484080104c10,0x221a011040400281,0x40925
};

#define NUM_BIT_BLOCKS (819)
#define MAX_PRIMES (10000)

static unsigned long g_primes[MAX_PRIMES];

/// Generate the list of primes from \ref g_prime_bits.
static void init_prime_table(void){
 unsigned long block_i, block, block_base, prime_i, prime, pos;

 prime_i = 0;
 g_primes[prime_i++] = 2;
 block_base = 3; // start at next prime
 for(block_i = 0; block_i < NUM_BIT_BLOCKS; block_i++){
  block = g_prime_bits[block_i];
  while(block){
   pos = (unsigned long)__builtin_ctzll(block); // get the position of LSB
   block &= block - 1; // clear only the LSB
   prime = block_base + 2 * pos; // calculate the prime
   g_primes[prime_i++] = prime;
  }
  block_base += 64 * 2;
 }
}

int main(void){
 unsigned long i, N, T;

 init_prime_table();
 scanf("%lu", &T);
 for(i = 0; i < T; i++){
  scanf("%lu", &N);
  printf("%lu\n", g_primes[N - 1]);
 }
}