计算一定范围内素数个数的算法

问题概述

问题：给定一个大整数N，计算开区间（1，N）的素数有多少？

• 算法1：根据素数性质，a不能整除小于等于根号a的所有整数，则必为素数，从1到N遍历找出所有素数。
• 算法2：素数筛选法，先剔除2的倍数，再剔除剩余的数中第一个数的倍数，直到剩余的数中第一个数大于根号N，此时剩下的数必全部为素数。

算法实现

#include 
#include 
#include 
#include 
#include #undef  TRUE
#define TRUE    1
#undef  FALSE
#define FALSE   0typedef int BOOL32;// a不能整除小于等于根号a的所有整数，则必为素数
void ChoosePrimeNumber_Slow(int dwTestSize)
{BOOL32* pbNumber = new BOOL32[dwTestSize];if (NULL == pbNumber){printf("[ChoosePrimeNumber_Slow] New Error!\n");return;}memset(pbNumber, 0, dwTestSize*sizeof(int));int dwIndex, dwLoop = 0;*(pbNumber+2) = TRUE;for(dwIndex=3; dwIndex<dwTestSize; dwIndex++){ for(dwLoop=2; dwLoop<= dwIndex; dwLoop++){if(dwIndex%dwLoop==0) break;if (dwLoop > (int)sqrt((double)dwIndex)){*(pbNumber+dwIndex) = TRUE;break;}}}	// 计算素数个数int dwNum = 0;for(dwIndex=2; dwIndex<dwTestSize; dwIndex++) {if(*(pbNumber+dwIndex))dwNum++;}printf("less than %d, there are %d prime number!\n", dwTestSize, dwNum);delete []pbNumber;return;
}// 素数筛选法
void ChoosePrimeNumber_Fast(int dwTestSize)
{BOOL32* pbNumber = new BOOL32[dwTestSize];
//	BOOL32* pbNumber = (BOOL32*) malloc(sizeof(BOOL32)*dwTestSize);if (NULL == pbNumber){printf("[ChoosePrimeNumber_Fast] New Error\n");return;}	memset(pbNumber, 0, dwTestSize*sizeof(int));int dwIndex, dwLoop = 0;*(pbNumber+2) = TRUE;for(dwIndex=3; dwIndex<dwTestSize; dwIndex++){if(0 != dwIndex%2) *(pbNumber+dwIndex)=TRUE;else*(pbNumber+dwIndex)=FALSE;}for(dwIndex=3; dwIndex<=(int)sqrt((double)dwTestSize); dwIndex++){if(*(pbNumber + dwIndex)){for(dwLoop=dwIndex+dwIndex; dwLoop<dwTestSize; dwLoop+=dwIndex) *(pbNumber+dwLoop)=FALSE;}}// 计算素数个数int dwNum = 0;for(dwIndex=2; dwIndex<dwTestSize; dwIndex++){if( *(pbNumber+dwIndex))dwNum++;}	printf("less than %d, there are %d prime number!\n", dwTestSize, dwNum);delete []pbNumber;
//	free(pbNumber);return;
}///
int main()
{clock_t cBegin, cTime = 0;int dwTestNum = 10000;for (int dwloop = 0; dwloop<5; dwloop++){cBegin = clock();ChoosePrimeNumber_Slow(dwTestNum);cTime = clock() - cBegin;#ifndef  WIN32cTime=cTime/1000;
#endifprintf("[%d] Method ChoosePrimeNumber_Slow spend %d ms.\n\n", dwloop, cTime);cBegin = clock();ChoosePrimeNumber_Fast(dwTestNum);cTime = clock() - cBegin;#ifndef  WIN32cTime=cTime/1000;
#endifprintf("[%d] Method ChoosePrimeNumber_Fast spend %d ms.\n\n", dwloop, cTime);dwTestNum = dwTestNum*10;}return 0;
}

运行结果

• CPU：Intel Core i3 2120
• RAM：2G

less than 10000, there are 1229 prime number!
[0] Method ChoosePrimeNumber_Slow spend 2 ms.less than 10000, there are 1229 prime number!
[0] Method ChoosePrimeNumber_Fast spend 0 ms.less than 100000, there are 9592 prime number!
[1] Method ChoosePrimeNumber_Slow spend 41 ms.less than 100000, there are 9592 prime number!
[1] Method ChoosePrimeNumber_Fast spend 1 ms.less than 1000000, there are 78498 prime number!
[2] Method ChoosePrimeNumber_Slow spend 973 ms.less than 1000000, there are 78498 prime number!
[2] Method ChoosePrimeNumber_Fast spend 32 ms.less than 10000000, there are 664579 prime number!
[3] Method ChoosePrimeNumber_Slow spend 23846 ms.less than 10000000, there are 664579 prime number!
[3] Method ChoosePrimeNumber_Fast spend 398 ms.less than 100000000, there are 5761455 prime number!
[4] Method ChoosePrimeNumber_Slow spend 643918 ms.less than 100000000, there are 5761455 prime number!
[4] Method ChoosePrimeNumber_Fast spend 4695 ms.Press any key to continue

算法分析

从运行结果显而易见，算法2效率要远远高于算法1。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！