Instantly share code, notes, and snippets.

# nekosan/prime.cppSecret Created May 14, 2015

10^7番目の素数を求めるプログラム
 #include #include #include #include using namespace std; const unsigned int SOLVE_MAX = 179424680 / 6 + 1; const unsigned int SOLVE_VALUE = 10000000; const unsigned int SEARCH_MAX = static_cast(sqrt(SOLVE_MAX * 6)) + 1; int main() { cout << "Calclate Start" << endl; const auto startTime = chrono::system_clock::now(); static unsigned char prime[SOLVE_MAX]; unsigned int search = 0; unsigned int i; unsigned int s = 1; unsigned int i_1; unsigned int i_5; unsigned int j_1; unsigned int j_5; for(i = 1; i < SOLVE_MAX; i++){ prime[i] = 0x11; } prime[0] = 0x10; //下位ビットは+1,上位ビットは+5 while(s <= SEARCH_MAX){ if(prime[search] & 0x01){ i_1 = search + s; while(i_1 < SOLVE_MAX){ prime[i_1] &= 0x10; i_1 += s; } i_5 = (5 * s - 5) / 6; while(i_5 < SOLVE_MAX){ prime[i_5] &= 0x01; i_5 += s; } } if(prime[search] & 0x10){ j_5 = search + s + 4; while(j_5 < SOLVE_MAX){ prime[j_5] &= 0x01; j_5 += s + 4; } j_1 = (5 * (s + 4) - 1) / 6; while(j_1 < SOLVE_MAX){ prime[j_1] &= 0x10; j_1 += s + 4; } } s += 6; search += 1; } unsigned int count = 2; for(i = 0; count < SOLVE_VALUE; i++){ count += (prime[i] & 0x01) + ((prime[i] & 0x10) >> 4); } i--; if(prime[i] == 0x01){ cout << i * 6 + 1 << endl; } else if(prime[i] == 0x10){ cout << i * 6 + 5 << endl; } const auto finishTime = chrono::system_clock::now(); const auto time = finishTime - startTime; cout << "Time[ms]: " << chrono::duration_cast(time).count() << endl; }