// Prime.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "stdlib.h"
#include <Windows.h>
#include <time.h>
/*------------------------------------------------
* [+FUNCTION+]
*
* NAME: GetPrimeCount
* DESC: To count how many primes to be stored
* PARA:
* ulPara: The number you want to find all
* primes less than
* AUTH: lonestep@gmail.com
*
*-[MODIFICATION LOG(S)]---------------------------
*
*/
ULONG GetPrimeCount( ULONG ulPara )
{
if (ulPara <= 536870911UL)
return 28192752UL;
else if (ulPara <= 1073741822UL)
return 54400030UL;
else if ( ulPara <= 1610612733UL)
return 79952416UL;
else if (ulPara <= 2147483644UL)
return 105097566UL;
else if ( ulPara <= 2684354555UL)
return 129949343UL;
else if(ulPara <= 3221225466UL)
return 154570518UL;
else if(ulPara <= 3758096377UL)
return 179006097UL;
else if(ulPara <= 4294967295UL)
return 189961814UL;
return 0UL; /* Never */
}
/*------------------------------------------------
* [+FUNCTION+]
*
* NAME: IsPrime
* DESC: Decide whether ulNumber is a prime,
* pulPrimes is all primes that have
* been found, ulPrimCnt is the prime
* count of pulPrimes.
* AUTH: lonestep@gmail.com
*
*-[MODIFICATION LOG(S)]---------------------------
*
*/
BOOL IsPrime(ULONG ulNumber, PULONG pulPrimes, ULONG ulPrimCnt )
{
ULONG i;
if (ulNumber < 2 || pulPrimes == NULL || ulPrimCnt == 0)
{
return FALSE;
}
for(i = 0; i < ulPrimCnt; i++)
{
if ( ulNumber%pulPrimes[i-1] == 0 )
{
return FALSE;
}
}
return TRUE;
}
/*------------------------------------------------
* [+FUNCTION+]
*
* NAME:AllPrimes
* DESC:Find all primes that smaller than
* ulNumber, if pFile is NOT NULL,
* then write the result to pFile
*
* AUTH: lonestep@gmail.com
*
*-[MODIFICATION LOG(S)]---------------------------
*
*/
PULONG AllPrimes(ULONG ulNumber, PCHAR pFile = NULL)
{
ULONG ulCur = 0;
ULONG ulPrimeCnt = 1;
if (ulNumber <= 2)
{
return NULL;
}
ULONG ulGetCnt = GetPrimeCount(ulNumber);
PULONG pulPrimes = (PULONG)malloc(ulGetCnt*sizeof(ULONG));
if (pulPrimes == NULL)
{
return NULL;
}
pulPrimes[0] = 2UL;
for (ulCur = 3; ulCur <ulNumber; ulCur++)
{
if (IsPrime(ulCur, pulPrimes, ulPrimeCnt))
{
pulPrimes[ulPrimeCnt] = ulCur;
ulPrimeCnt ++;
}
}
memset(&pulPrimes[ulPrimeCnt], 0, ulGetCnt - ulPrimeCnt);
if (pFile != NULL)
{
DWORD nRet =0;
DWORD nBytes = 0;
HANDLE hFile = CreateFile(pFile,
GENERIC_WRITE,
0,
0,
CREATE_ALWAYS,
0,
0);
if (hFile == INVALID_HANDLE_VALUE)
{
printf("Create File Failed:%d \n",GetLastError());
return pulPrimes;
}
nRet = WriteFile(hFile, pulPrimes, ulPrimeCnt, &nBytes, 0);
if (nRet == 0)
{
printf("Write File Failed:%d\n",GetLastError());
}
CloseHandle(hFile);
}
return pulPrimes;
}
int main(int argc, char* argv[])
{
UINT time = GetTickCount();
PULONG pPrimes = AllPrimes(100000,"1.txt");
if ( pPrimes != NULL)
{
UINT nNdx = 0;
while (pPrimes[nNdx] != '\0')
{
printf("%lu\t", pPrimes[nNdx]);
nNdx++;
}
free(pPrimes);
}
time = GetTickCount() -time;
printf("time:%d ms.\n", time);
system("pause");
return 0;
}