求1~n范围内的素数

素数：素数又称质数，是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。

判断素数的方法：理论可证，用一个数分别去除2到sqrt(这个数)，如果能被整除，则表明此数不是素数，反之是素数。

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

void prime_number(int x);//求1~x范围内素数
int *primes_array = NULL;

int main(int argc, char *argv[]) 
{
	prime_number(100);//求100以内的素数
}

void prime_number(int x)//求1~x范围内素数 
{ 
	int i,j,p=0,num=0;
	
	//计算范围内所含素数个数 
	for(i=1;i<=x;i++)
	{
		for(j=2;j<=sqrt(i);j++)
		{
			if(i%j==0)
			break;
		}
		if(j>sqrt(i))
		num++;
	}	
	printf("%d以内的素数有%d个\n",x,num);
	
	//动态分配数组，将范围内素数存入数组 
	primes_array = (int*)malloc(num*sizeof(int));
	for(i=1;i<=x;i++)
	{
		for(j=2;j<=sqrt(i);j++)
		{
			if(i%j==0)
			break;
		}
		if(j>sqrt(i))
		primes_array[p++]=i;
	}
	
	//输出数组内素数 
	for(i=0;i<p;i++)
	printf("%d ",primes_array[i]);
}