[UVa][ Volume IV ] 406 - Prime Cuts

UVa Volume IV  406 - Prime Cuts


題目來源 : Prime Cuts

解題 :

常見的質數題目，一般來說都會用到埃氏篩法(Sieve of Eratosthenes)來找出質數。

首先，我建立一個prime -- 大小為n的一維boolean陣列，代表某數字是否為質數。

埃氏篩法(Sieve of Eratosthenes)作法如下 :

若一個正整數為另一個正整數的倍數，則這個整數必定不是質數。
所以，從最小質數2開始，將所有2的倍數(不包含2)標記為⌈非質數⌋。
接著，往下下一個沒有被標記成質數的數字3，再將3的倍數(不包含3)標記為⌈非質數⌋。
以此類推下去，直到找出所有小於等於n的質數。

找出所有質數後，只要根據質數的數量，並且依找題目要求輸出中間2*C (或是 2*C - 1)個質數

參考解答(C++)

	#include <iostream>
	using namespace std;
	int main(void)
	{
	int n, c;
	while (cin >> n >> c)
	{
	// 變數初始化
	bool *prime = new bool[n];
	for (int i = 0; i < n; i++)
	{
	prime[i] = true;
	}
	// 紀錄哪些數是質數
	int num = 1;
	for (int i = 2; i <= n; i++)
	{
	if (prime[i - 1])
	{
	num++;
	for (int j = 2; j * i <= n; j++)
	{
	prime[j * i - 1] = false;
	}
	}
	}
	cout << n << " " << c << ":";
	int i, x, p = 2 * c - (num % 2 ? 1 : 0);
	// 跳過不需輸出的質數
	x = 0;
	for (i = 0; x < (num - p) / 2; i++)
	{
	if (prime[i])
	{
	x++;
	}
	}
	// 開始輸出的質數
	x = 0;
	for (; x < p && i < n; i++)
	{
	if (prime[i])
	{
	cout << " " << i + 1;
	x++;
	}
	}
	cout << endl
	<< endl;
	}
	system("pause");
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub