#include <string>
#include <sstream>
#include <time.h>
#include <algorithm>
#include <vector>
#include <iostream>
#include <hash_map>
using namespace std;


class compare
{
	vector<int> dataVector;
	vector<int> findData;
	hash_map<int, int> dataHash;
public:
	compare();
	~compare(void);
	void generalPrime();
	void findTest();
	void binSearch();
	void hashTest();
};

compare::compare()
{
	generalPrime();
}


compare::~compare(void)
{
	findData.clear();
	dataVector.clear();
}

void compare::findTest()
{
	clock_t startTime = clock();
	vector<int>::iterator result;
	int exist = 0;
	for (vector<int>::iterator it = findData.begin(); it < findData.end(); it++)
	{
		result = find(dataVector.begin(), dataVector.end(), *it);
		if (result != dataVector.end())
		{
			//查找成功
			exist++;
		}
	}
	clock_t endTime = clock();
	cout << "exist num: " << exist << " find time " << (double)(endTime - startTime)/CLOCKS_PER_SEC*1000 << "ms" <<endl;
}

void compare::binSearch()
{
	int start;
	int end;
	int middle;
	int exist = 0;
	clock_t startTime = clock();
	for (vector<int>::iterator it = findData.begin(); it < findData.end(); it++)
	{
		start = 0;
		end = dataVector.size() - 1;
		middle = (start + end) / 2;
		while (start <= end)
		{
			if (*it < dataVector[middle])
			{
				end = middle - 1;
			}
			else if (*it > dataVector[middle])
			{
				start = middle + 1;
			}
			else
			{
				break;
			}
			middle = (start + end) / 2;
		}
		if (start <= end)
		{
			exist++;
		}
	}
	clock_t endTime = clock();
	cout << "exist num: " << exist << " binsearch time: " << (double)(endTime - startTime)/CLOCKS_PER_SEC * 1000 << "ms" << endl;
}

void compare::generalPrime()
{
	int maxPrime = 99999;
	int flag;
	vector<bool> visited(maxPrime, true);
	for (int i = 2; i < maxPrime; ++i)
	{
		findData.push_back(i);
		if (visited[i])
		{
			dataVector.push_back(i);
			dataHash[i] = 1;
			flag = i;
			for (int ii = 2, flag = i * ii; flag < maxPrime; ++ii, flag *= ii)
			{
				visited[flag] = false;
			}
		}
	}
}

void compare::hashTest()
{
	clock_t startTime = clock();
	int exist = 0;
	vector<int>::iterator result;
	for (vector<int>::iterator it = findData.begin(); it < findData.end(); it++)
	{
		if (dataHash.find(*it) != dataHash.end())
		{
			exist++;
		}
	}
	clock_t endTime = clock();
	cout << "exist num: " << exist << " hash time " << (double)(endTime - startTime)/CLOCKS_PER_SEC*1000 << "ms" << endl;
}
int main()
{
	compare com;
	com.findTest();
	com.binSearch();
	com.hashTest();
	return 1;
}