欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

筛选法求质数

程序员文章站 2024-03-14 21:08:32
...
#include <stdio.h>
#include <stdlib.h>
/* 筛选法求质数 */

void f(int x);

int main()
{
	int x;
	puts("请输入一个数:");
	scanf("%d",&x);
	f(x);

	return 0;
}

void f(int x)
{
	int k = 0;
	int *p = (int*)malloc(sizeof(int) * x);

	for (int i=2;i<x;i++)
	{
		*(p + i) = 1;
	}

	for (int i=2;i*i<x;i++)  //筛除合数
	{
		for (int j=i;i*j<x;j++) //能分解为i和j的数即是合数
		{
			*(p + i*j) = 0;
		}
	}

	for (int i=0;i<x;i++)
	{
		if(*(p + i) == 1)
		{
			k++;
			printf("%-4d",i);
		}
	}
	printf("\n%d内,共有%d个质数\n",x,k);
}