#include <iostream>
int main(){
const long long int n=20313; //find primes up to n*64, where n is an approximation
int primes[101000]; //We want the 100000th prime, plus some extra because of the approximation used above
unsigned long long int numbers[n]; //create the array so we're allocated the space
int* ptr=(int *)numbers;
int* prime=(int *)primes; //get pointers to the arrays
primes[0]=2;
long unsigned int x=1; // dummy variable used in debugging
long long unsigned int tab[129]={0, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767, 65535, 131071, 262143, 524287, 1048575, 2097151, 4194303, 8388607, 16777215, 33554431, 67108863, 134217727, 268435455, 536870911, 1073741823, 2147483647, 4294967295, 8589934591, 17179869183, 34359738367, 68719476735, 137438953471, 274877906943, 549755813887, 1099511627775, 2199023255551, 4398046511103, 8796093022207, 17592186044415, 35184372088831, 70368744177663, 140737488355327, 281474976710655, 562949953421311, 1125899906842623, 2251799813685247, 4503599627370495, 9007199254740991, 18014398509481983, 36028797018963967, 72057594037927935, 144115188075855871, 288230376151711743, 576460752303423487, 1152921504606846975, 2305843009213693951, 4611686018427387903, 9223372036854775807, 18446744073709551615, 18446744073709551614, 18446744073709551613, 18446744073709551611, 18446744073709551607, 18446744073709551599, 18446744073709551583, 18446744073709551551, 18446744073709551487, 18446744073709551359, 18446744073709551103, 18446744073709550591, 18446744073709549567, 18446744073709547519, 18446744073709543423, 18446744073709535231, 18446744073709518847, 18446744073709486079, 18446744073709420543, 18446744073709289471, 18446744073709027327, 18446744073708503039, 18446744073707454463, 18446744073705357311, 18446744073701163007, 18446744073692774399, 18446744073675997183, 18446744073642442751, 18446744073575333887, 18446744073441116159, 18446744073172680703, 18446744072635809791, 18446744071562067967, 18446744069414584319, 18446744065119617023, 18446744056529682431, 18446744039349813247, 18446744004990074879, 18446743936270598143, 18446743798831644671, 18446743523953737727, 18446742974197923839, 18446741874686296063, 18446739675663040511, 18446735277616529407, 18446726481523507199, 18446708889337462783, 18446673704965373951, 18446603336221196287, 18446462598732840959, 18446181123756130303, 18445618173802708991, 18444492273895866367, 18442240474082181119, 18437736874454810623, 18428729675200069631, 18410715276690587647, 18374686479671623679, 18302628885633695743, 18158513697557839871, 17870283321406128127, 17293822569102704639, 16140901064495857663, 13835058055282163711, 9223372036854775807};
//int * lkup=(int *)tab; //create lookup table and get pointer
__asm__(
"mov rax, 0xAAAAAAAAAAAAAAAA \n" //multiples of 2 already unset
"mov rdi, %1 \n" //point at numbers array
"mov rcx, %2 \n" // which has length n qwords
"rep stosq \n" //fill as efficiently as possible with rax
"mov rdi, %1 \n"
"xor [rdi+4], dword ptr 0x80000000 \n" //point at start of array again, then unset 2
//initialise array with 2 already done
"mov rax, 0x8000000000000000\n" //set first bit
"mov rcx, 0x01\n" //set prime counter to 1
"jmp loop\n" //enter loop


"start:\n"
"mov rax, 0x0000000000000001\n" //needs to roll around to the first bit after the rcr 2
"add rdi, 0x08\n" //move rdi 8 bytes onwards
"sub rcx, 0x02\n" //subtract 2 from prime counter else a number gets skipped
"loop:\n"
"add rcx, 0x02\n" //add 2 to prime counter
"rcr rax, 0x02\n" //rotate bit across 2
"jc start \n" //if carry set, move to next qword
"test [rdi], rax \n" //test if the bit set in rax is present, indicating a prime
"jz loop\n"  //if not, check next odd number

//prime found

"push rax\n" //preserve the registers needed above
"push rcx\n"
"push rdi\n"
"add %3, qword ptr 0x04\n" //increment pointer to primes array
"mov rdi, %3\n"
"mov [rdi], rcx\n"
//move prime into array
"cmp rcx, 0x40\n" //different methods for different size primes
"jg over64\n" 

//for primes <64
"mov rax, 0x40\n"
"div cl\n" //divide 64 by the prime
"mov dx, ax\n" //move quotient and remainder to dx
"xor rax, rax\n" //clear ax
"andbyte:\n"
"add rax, 0x01\n" //set rightmost bit
"ror rax, cl\n" //rotate into position


"dec dl\n" //decrease quotient
"jnz andbyte\n" 
//create qword to be anded
//qword is now in rax


"mov rsi, rcx\n" //save prime to rsi
"mov cl,dh\n" //move remainder (also the modulus) into cl
"mov rbx, rcx\n" 
"inc rbx\n" //move remainder to rbx and add one, rbx is now the number of 1's on the right of rax

"not rax\n"
//rax now holds a number such that every prime'th bit is 0, so that multiples of the prime get cleared by an and
"mov rdi, %1\n" //point to numbers array
"mov rdx, %2\n" //number of qwords to pass over

"andloop:\n"

"and [rdi], rax \n" //clear multiples of the prime
"add rdi, 0x08\n" //move to next qword
"shl rax, cl\n" //shift rax so it lines up with the next byte
"add rbx, rcx\n" //increase how many 1's are on the right

//do ((1 << mod)-1) xor (1 << mod2)
//use lookup tables for each
"cmp rbx, rsi\n"
"jl mod1\n"
"sub rbx, rsi\n" //rbx is using arithmetic modulo prime
"mod1:\n"
"or rax, [%4+rcx*8]\n" //set rightmost bits depending on the modulus

"and rax, [%4+512+rbx*8]\n" //unset a bit so the necessary pattern is preserved

"dec rdx\n"
"jnz andloop \n"
"jmp end\n"

"over64:\n" //for primes over 64
"cmp rcx, 1140\n" //compare to sqrt(max), skip if greater
"jg end\n"

"mov rsi, rcx\n" //preserve prime
"and rcx, 0x3F\n" //take modulus with 64
"shr rsi, 0x6\n" //divide by 64
"mov rax, 0x1\n"
"ror rax, cl\n" //rotate bit into right place
"mov rdx, %2\n" //number of qwords to check
"sub rdx, rsi\n" //to prevent overflow into primes array
"not rax\n" 
"mov rdi, %1\n" //point at numbers array
"mov rbx, rcx\n" //rbx counts how many bits have been shifted right
"lea rdi, [rdi+rsi*8]\n" //start at the qword containing the prime
"shl rsi, 0x1\n"
"shl rcx, 0x1\n"
"cmp rcx, 0x40\n"
"jl loop1\n"
"add rsi, 0x01\n"
"sub rcx, 0x40\n"

"loop1:\n" 
"and [rdi], rax\n" //unset multiples of the prime
"add rbx, rcx\n" 
"ror rax, cl\n" //rotate rax as necessary
"lea rdi, [rdi+rsi*8]\n" //move (prime/64) qwords across to next qword which contains a multiple of the prime
"cmp rbx, 0x40\n" //if rbx overflows then we need to skip an additional qword
"jl temp\n"
"add rdi, 0x08\n" //next qword
"sub rbx, 0x40\n"
"dec rdx\n" //one less loop

"temp:\n"
"sub rdx, rsi\n" //take however many qwords we skipped over
"jg loop1 \n"


"end:\n"
"pop rdi\n" //restore registers
"pop rcx\n"
"pop rax\n"
"cmp rcx, 1300000\n" //loop until we hit the number 1300000
"jl loop\n"


: "=m" (x)
: "m" (ptr), "i" (n), "m" (prime), "m" (tab)
: "rax", "rcx", "rdi", "rdx", "rbx", "rsi");

//std::cout << primes[100000];
}