Create a gist now

Instantly share code, notes, and snippets.

@nekosan /prime.cpp Secret
Created May 14, 2015

What would you like to do?
10^7番目の素数を求めるプログラム
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment