せんけいふるいほうそすう

まず最も一般的な素数を求める方法を紹介し,二層循環暴力解,時間複雑度O(n^2),データ量が大きい場合はこの方法は望ましくなく,コードは以下の通りである:

#include 

using namespace std;

int main()
{
	int i, j, prime[1005];
	for(i = 2; i < 1000; i++)
	{
		prime[i] = 0;
		for(j = 2; j < i; j++)  //   i    sqrt(i)
		{
			if(i % j == 0) break;
		}
		if(j == i) prime[i] = 1;  //prime[i] = 1      。 
		if(prime[i]) printf("%d ", i);
	}
	return 0; 
}

以下の方法はEratosthenesふるい法を用い,時間複雑度はO(nlogn)であり,コードは以下の通りである:

#include 
#include 

using namespace std;

int main()
{
	int n, vis[1005] = {0};
	scanf("%d", &n); 
	int m = sqrt(n + 0.5);
	for(int i = 2; i <= m; i++)
	{
		if(!vis[i]) 
		for(int j = i * i; j <= n; j += i) vis[j] = 1;
	}
	for(int i = 2; i <= n; i++) if(!vis[i]) printf("%d ", i);
	return 0; 
}

この方法は、i=2で4、6、8、10、12、14、16、18などを繰り返し濾過し、i=3で9、12、15、18などを濾過し、ここで2回繰り返し濾過し、これが20以内の数で2回繰り返したので、後にどれだけの時間を浪費したかがわかる.3.最後の方法はオーラふるい法で、これも私が今見た最も速いアルゴリズムで、時間の複雑度はO(n)で、もし誰がもっと速いアルゴリズムがあれば教えてほしいです.コードは次のとおりです.

#include 

using namespace std;
int prime[1005], vis[1005], cnt = 0;
void func(){
	for(int i = 0; i <= 1000; i++) vis[i] = 0;
	vis[0] = vis[1] = 1;
	for(int i = 2; i <= 1000; i++)
	{
		if(!vis[i]) prime[cnt++] = i;
		for(int j = 0; j < cnt && prime[j] * i <= 1000; j++)
		{
			vis[prime[j] * i] = 1;
			if(i % prime[j] == 0) break;
		}
	}
}
int main()
{
	func();
	for(int i = 0; i < cnt; i++) printf("%d ", prime[i]);
	return 0;
}

この方法は非常に巧みで,素数ではなく繰り返しのないすべてのふるいをふるうことができ,興味のある人は自分でシミュレーションすることができる.