高效素数打表

首先给大家推荐一下我老师大神的人工智能教学网站。教学不仅零基础,通俗易懂,而且非常风趣幽默,还时不时有内涵黄段子!点这里可以跳转到网站

大家所知的素数打表时间复杂度几乎都是n2。

就是这种:

void init_prime()
{
	int i, j;
	for(i = 2;i <= sqrt(1000002.0); ++i)
	{
		if(!prime[i])
			for(j = i * i; j < 1000002; j += i)
				prime[j] = 1;
	}
	j = 0;
	for(i = 2;i <= 1000002; ++i)
		if(!prime[i]) 
			prime[j++] = i;
}

在网上搜到了另一种方法,效率提高了不少。巧妙之处还在研究中,等理解差不多就仔细分析一下。

下面是代码,大家可以发表一下自己的看法,交流交流。

代码如下:

/*
遇到素数需要打表时,先估算素数的个数:
num = n / lnx;
num为大概数字,越大误差越小(只是估计,用于估算素数表数组大小)
这个打表法效率貌似很高,网上说几乎达到了线性时间(不知道是真是假=。=)
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<ctime>
#include<algorithm>
using namespace std;
int n;
bool visit[10100000];
int prime[10000000];


void init_prim()
{
	memset(visit, true, sizeof(visit));
	int num = 0;
	for (int i = 2; i <= n; ++i)
	{
		if (visit[i] == true)
		{
			num++;
			prime[num] = i;
		}
		for (int j = 1; ((j <= num) && (i * prime[j] <= n));  ++j)
		{
			visit[i * prime[j]] = false;
			if (i % prime[j] == 0) break; //点睛之笔
		}
	}
}

int main()
{
	memset(prime, 0, sizeof(prime));
	int count = 0;
	cin>>n;
	init_prim();
	for(int i = 0; i <= n; ++i)
		if(prime[i])
		{
			cout<<prime[i]<<" ";
			count++;
		}
		cout<<endl;
		cout<<"素数个数为:"<<count<<endl;
}        

点这里可以跳转到人工智能网站

发表评论