Prime number 구하기 (multi thread)

1과 자기 자신 이외의 다른 양의 정수로 나누어지지 않는 1보다 큰 정수라고 하였습니다.

소수는 양의 약수로 1과 자신만을 가진 자연수 = 2개

 

 

 

주의 : 로직에는 소수의 누적 개수를 제대로 구했는지에 대한 확인 코드가 같이 들어있습니다

 

필자의 pc 에서 hardware_concurrency 값은24

 

vector<int> retV;

vector<vector<int>> range;

bool isPrime(int num)
{
	if (num == 0 || num == 1)
	{
		return false;
	}
	else if ( num == 2)
	{
		return true;
	}

	//int maxNum=sqrtl(num);
	for (int i=2; i*i <= num;++i)
	{
		if (num % i == 0)
		{
			return false;
		}
	}
	return true;
}



void primeCount(int start, int end, int i)
{
	int count = 0;
	for (int i=start;i<end;++i)
	{
		count +=isPrime(i);
	}

	retV[i] = count;
}


int verifyPrimeCount(int start, int end)
{
	int count = 0;

	for (int i = start; i < end; ++i)
	{
		if (isPrime(i))
		{
			count += 1;
		}
	}
	return count;
}




int main()
{


	//int count = 100'0000;	//=>	78498
	int count = 1'0000;		//=> 1229
	//int count = 1000;			//168
	//int count = 24 * 2 + 1;			
	//int count = 3;			
	//필자의 pc 코어는 
	//int count = 10;			//=> 4

	count += 1;		//해당 숫자 까지 임으로
	

	int jj = 0;
	int total = 0;
	int verifyCount = 0;

	retV.reserve(thread::hardware_concurrency());

	while (jj <= count)
	{

		int32 threadCount = thread::hardware_concurrency();
		verifyCount = verifyPrimeCount(0, count);

		//스레드가 구할 개수보다 더 많으면 분할 수치에 오류가 생김으로
		//코어가 많아봐야 24*2 정도 => 가정짐 기준
		//또는 hardware_concurrency 이 0 을 리턴할 수도 있다
		if (threadCount * 2 >= count)
		{
			threadCount = 1;
		}

		//int32 threadCount = 3;
// 		range.resize(threadCount + 1);
// 		for (auto& elem : range)
// 		{
// 			elem.resize(2);
// 		}

		retV.resize(threadCount + 1);

		vector<thread> threads;

		int divi = count / threadCount;
		for (int i = 0; i <= threadCount; ++i)
		{
			threads.push_back(thread([i, count, divi]()
			{
				//확인을 위한 분할 값
				//range[i][0] = divi * i;
				//range[i][1] = min(count, divi * (i + 1));

				primeCount(divi * i, min(count, divi * (i + 1)), i);
			}));
		}


		for (auto& th : threads)
		{
			th.join();
		}

		total = 0;
		total = std::accumulate(retV.begin(), retV.end(), 0);

		//총 소수개수
		//cout << total << std::endl;

		if (verifyCount != total)
		{
			int different = 0;
			different = 1;
		}

		++jj;
	}
    return 0;
}

이거보다 더 개선할 방향들은 있을 겁니다