暂时没有找到对应的力扣题

题目：

给定范围 n，找出其内所有的素数并且显示素数个数（0，1 不统计）

思路：

素数的概念：能被 1 及 自己 整除的数，比如 2，3，5；4 能被 2 整除，所以不是素数

方法一、暴力

给定数 n，依次除 n-1，n-2 ...

int countPrime(int range)
{
	printf("---BF----\n");
	int i,j;
	int cnt = 0;
	
	for(i=2; i<range; i++)
	{
		j = i-1;
		while(j >= 2)
		{
			if(i % j == 0)
				break;
			j--; 
		}
		if(j < 2)
		{
			cnt ++;
			printf("%d is prime.\n", i);
		}
	}
	
	return cnt;
}

方法二、Eratosthenes 筛选法

思想就是用一维数组对每个数字标记，如果是素数，那么素数的倍数一定不是

比如：2 是素数，2*2=4，2*3=6... 就不是素数，遍历时这些就不用进行判断了

做了一点优化，倍数关系

int countPrimeII(int range)
{
	printf("---Eratosthenes----\n");
	int cnt = 0;
	int len = range;
	int *mask = (int *)malloc(sizeof(int) * len);
	
	// init mask to 0:not prime, 1: is prime
	int i,j,k;
	for(i=0; i<len; i++)
	{
		mask[i] = 1;
	}
	
	for(i=2; i<range; i++) // check all non-prime
	{
		if(mask[i] == 1)
		{
			cnt++;
			
			for(k=i; i*k < range; k++)
			{
				mask[i*k] = 0;
			}
		}
	}
	
	for(i=2; i<len; i++)
	{
		if(mask[i] == 1)
			printf("%d is prime.\n", i);
	}
	
	free(mask);
	return cnt;
}

方法三、Hash

一个数如果可以拆分为多个数的乘积，那么这个数一定不是素数

比如：6=2*3，9=3*3，24=2*12=2*3*4=2*3*2*2

可以看出最终都是素数的最小分解

那么结论是如果这个数去除已知的素数，不能整除，那么这个数就是素数

所以我们只需要构建素数的hash，判断数能否整除这些 hash 元素，如果是素数，那么将该数加入hash

hash 的第一个元素用于存储目前hash的素数个数

int checkPrime(int *hash, int num)
{
	int i;
	int hashLen = hash[0];
	
	for(i=1; i<=hashLen; i++)
	{
		if(num % hash[i] == 0)
			return 0;	
	}
	
	return 1;
}

void addPrime(int *hash, int num)
{
	int idx = hash[0] + 1;
	hash[idx] = num;
	hash[0]++;
}

int countPrimeIII(int range)
{
	printf("---Hash----\n");
	int cnt = 0;
	int len = range / 2;
	int *hash = (int *)malloc(sizeof(int) * len);
	
	// init hash, hash[0]: prime nums in hash
	int i;
	for(i=0; i<len; i++)
		hash[i] = 0;
		
	for(i=2; i<range; i++)
	{
		if( checkPrime(hash, i) ) // is prime, add it to hash
		{
			cnt++;
			addPrime(hash,i);
		}
	}
	
	for(i=1; i<=hash[0]; i++)
	{
		printf("%d is prime.\n", hash[i]);
	}
	
	free(hash);
	return cnt;
}

查看更多刷题笔记