10^7番目の素数を求めるプログラム

prime.cpp

#include<iostream>
#include<cmath>
#include<chrono>
#include<limits>

using namespace std;

const unsigned int SOLVE_MAX = 179424680 / 6 + 1;
const unsigned int SOLVE_VALUE = 10000000;
const unsigned int SEARCH_MAX = static_cast<unsigned int>(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<chrono::milliseconds>(time).count() << endl;
}