ThreadPrimes.c

#include <stdio.h>
#include <math.h>
#include <Windows.h>

#define MAX_THREADS 32

typedef struct PrimeData {
	unsigned long min;
	unsigned long max;
	unsigned long count;
	double time;
	int* primes;
} PRIMEDATA, * PPRIMEDATA;

typedef BOOL(WINAPI* LPFN_GLPI)(
    PSYSTEM_LOGICAL_PROCESSOR_INFORMATION,
    PDWORD);

// Helper function to count set bits in the processor mask.
DWORD count_set_bits(ULONG_PTR bitMask)
{
    DWORD LSHIFT = sizeof(ULONG_PTR) * 8 - 1;
    DWORD bitSetCount = 0;
    ULONG_PTR bitTest = (ULONG_PTR)1 << LSHIFT;
    DWORD i;

    for (i = 0; i <= LSHIFT; ++i)
    {
        bitSetCount += ((bitMask & bitTest) ? 1 : 0);
        bitTest /= 2;
    }

    return bitSetCount;
}

/* https://docs.microsoft.com/en-us/windows/win32/api/sysinfoapi/nf-sysinfoapi-getlogicalprocessorinformation */
int _cdecl get_logical_processor_count()
{
    LPFN_GLPI glpi;
    BOOL done = FALSE;
    PSYSTEM_LOGICAL_PROCESSOR_INFORMATION buffer = NULL;
    PSYSTEM_LOGICAL_PROCESSOR_INFORMATION ptr = NULL;
    DWORD returnLength = 0;
    DWORD logicalProcessorCount = 0;
    DWORD processorCoreCount = 0;
    DWORD byteOffset = 0;

    glpi = (LPFN_GLPI)GetProcAddress(
        GetModuleHandle(TEXT("kernel32")),
        "GetLogicalProcessorInformation");
    if (NULL == glpi)
    {
        printf(("\nGetLogicalProcessorInformation is not supported.\n"));
        return (1);
    }

    while (!done)
    {
        DWORD rc = glpi(buffer, &returnLength);

        if (FALSE == rc)
        {
            if (GetLastError() == ERROR_INSUFFICIENT_BUFFER)
            {
                if (buffer)
                    free(buffer);

                buffer = (PSYSTEM_LOGICAL_PROCESSOR_INFORMATION)malloc(
                    returnLength);

                if (NULL == buffer)
                {
                    printf(("\nError: Allocation failure\n"));
                    return (2);
                }
            }
            else
            {
                printf(("\nError %d\n"), GetLastError());
                return (3);
            }
        }
        else
        {
            done = TRUE;
        }
    }

    ptr = buffer;

    while (byteOffset + sizeof(SYSTEM_LOGICAL_PROCESSOR_INFORMATION) <= returnLength)
    {
        switch (ptr->Relationship)
        {
        case RelationProcessorCore:
            processorCoreCount++;

            // A hyperthreaded core supplies more than one logical processor.
            logicalProcessorCount += count_set_bits(ptr->ProcessorMask);
            break;

        default:
            break;
        }
        byteOffset += sizeof(SYSTEM_LOGICAL_PROCESSOR_INFORMATION);
        ptr++;
    }

    free(buffer);

    return logicalProcessorCount;
}


 DWORD WINAPI calculate_prime_range(LPVOID lpParam) {
	LARGE_INTEGER StartingTime, EndingTime, ElapsedMicroseconds;
	LARGE_INTEGER Frequency;
	size_t allocSize = 100;

	PPRIMEDATA pDataArray = (PPRIMEDATA)lpParam;
	pDataArray->count = 0;

	QueryPerformanceFrequency(&Frequency);
	QueryPerformanceCounter(&StartingTime);

	pDataArray->primes = (int*)malloc(allocSize * sizeof(DWORD));

	if (!pDataArray->primes) {
		printf("malloc error!\n");
		exit(-1);
	}
	for (int j = (int)pDataArray->min; j < (int)pDataArray->max; j++) {
		if (j == 2 || j == 3) {
			pDataArray->primes[pDataArray->count++] = j;
		}
		else {
			for (int f = 2; f * f <= j; f++) {
				if (j % f == 0) {
					break;
				}
				else if ((double)f + 1 > sqrt(j)) {
					if (pDataArray->count == allocSize - 1) {
						allocSize += 100;
						int* tmpPtr;
						tmpPtr = (int*)realloc(pDataArray->primes, allocSize * sizeof(DWORD));
						if (!tmpPtr) {
							printf("realloc() failed!\n");
							exit(-1);
						}

						pDataArray->primes = tmpPtr;
					}

					pDataArray->primes[pDataArray->count++] = j;
				}
			}
		}
	}

	QueryPerformanceCounter(&EndingTime);
	ElapsedMicroseconds.QuadPart = EndingTime.QuadPart - StartingTime.QuadPart;
	ElapsedMicroseconds.QuadPart *= 1000000;
	ElapsedMicroseconds.QuadPart /= Frequency.QuadPart;

	// Compute ellapsed time.
	pDataArray->time = (double)ElapsedMicroseconds.QuadPart;

	return 0;
}

int main(int argc, char *argv[])
{
	unsigned long thread_count, min, max;
	PPRIMEDATA pDataArray[MAX_THREADS];
	HANDLE  hThreadArray[MAX_THREADS] = {};

	printf("Please enter the number of threads to create:\n");
	scanf_s("%lu", &thread_count);

	unsigned long logical_processor_count = get_logical_processor_count();

	if (thread_count > MAX_THREADS || thread_count > logical_processor_count) {
		printf("You've entered a value too high. Thread count has been limited to the number of logical processors available: %lu\n", logical_processor_count);
		thread_count = logical_processor_count;
	}

	printf("Using %d threads.\n", thread_count);

	printf("Please enter a range to calculate the amount of primes (e.g. 3-10000):\n");
	scanf_s("%lu-%lu", &min, &max);

	for (unsigned long i = 0; i < thread_count; i++) {
		pDataArray[i] = (PPRIMEDATA)HeapAlloc(GetProcessHeap(), HEAP_ZERO_MEMORY, sizeof(PRIMEDATA));

		// even split the range amongst the thread count
		unsigned long block = (max / thread_count);

		if (i == 0) {
			pDataArray[i]->min = min;
			pDataArray[i]->max = block;
		}
		else if (i == thread_count - 1) {
			pDataArray[i]->min = 1 + (block * i);
			pDataArray[i]->max = max; // to avoid miscalculation if not evenly divided 
		}
		else {
			pDataArray[i]->min = 1 + (block * i);
			pDataArray[i]->max = (block * i) + block;
		}

		printf("Calling thread with range: %lu - %lu\n", pDataArray[i]->min, pDataArray[i]->max);
		hThreadArray[i] = CreateThread(NULL, NULL, calculate_prime_range, pDataArray[i], 0, NULL);

		if (hThreadArray[i] == NULL)
		{
			printf("Error in CreateThread!\n");
			exit(-1);
		}
	}

	WaitForMultipleObjects(thread_count, hThreadArray, TRUE, INFINITE);
	
	double totalTime = 0;
	unsigned long totalCount = 0;

	for (unsigned long i = 0; i < thread_count; i++) {
		for (unsigned long x = 0; x < pDataArray[i]->count; x++) {
			printf("%d ", pDataArray[i]->primes[x]);
		}
		printf("\nthread: %lu count: %lu time elapsed: %f\n", i, pDataArray[i]->count, pDataArray[i]->time);
		totalCount += pDataArray[i]->count;
		totalTime += pDataArray[i]->time;
	}


	printf("\nTotal amount of prime numbers within %lu-%lu is %lu. (Calculation time: %f)\n", min, max, totalCount, totalTime);

	for (unsigned long i = 0; i < thread_count; i++) {
		CloseHandle(hThreadArray[i]);

		if (pDataArray[i] != NULL)
		{
			free(pDataArray[i]->primes);
			pDataArray[i]->primes = NULL;

			HeapFree(GetProcessHeap(), 0, pDataArray[i]);
			pDataArray[i] = NULL;
		}
	}

}