結果

問題 No.12 限定された素数
ユーザー OnjuOnju
提出日時 2015-02-10 04:06:57
言語 C++11
(gcc 11.4.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,483 bytes
コンパイル時間 379 ms
コンパイル使用メモリ 56,588 KB
最終ジャッジ日時 2023-08-15 22:32:14
合計ジャッジ時間 728 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ（β）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp: In function ‘std::vector<Prime>* getPrime(int)’:
main.cpp:29:16: error: ‘sqrt’ was not declared in this scope
  int sn = (int)sqrt(N);
                ^~~~
main.cpp:29:16: note: suggested alternative: ‘qsort’
  int sn = (int)sqrt(N);
                ^~~~
                qsort

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <vector>
#define N_MAX 10
#define L_MAX 5000000
using namespace std;

typedef struct
{
	int value;
	int usednum;
}Prime;

int bitNum(int n)
{
	int bit = 0;
	while (n)
	{
		bit |= 1 << (n % 10);
		n /= 10;
	}
	return bit;
}

vector<Prime>* getPrime(int N)
{
	auto list = new bool[N + 1];
	auto prime = new vector<Prime>();
	int sn = (int)sqrt(N);

	list[0] = list[1] = false;
	for (int i = 2; i <= N; ++i)
		list[i] = true;

	for (int i = 2; i <= sn; ++i)
	{
		if (list[i])
		{
			int jmax = N / i;
			for (int j = i; j <= jmax; ++j)
				list[i*j] = false;
		}
	}

	for (int i = 2; i <= N; ++i)
	{
		if (list[i])
		{
			prime->push_back(Prime{ i, bitNum(i) });
		}
	}

	delete[] list;

	return prime;
}

int main()
{
	int N, A[N_MAX], AA = 0, revAA, LK = -1;
	auto prime = getPrime(L_MAX);
	int num;
	cin >> N;

	for (int i = 0; i < N; ++i)
	{
		cin >> A[i];
		AA |= 1 << A[i];
	}
	revAA = ~AA;

	//全使用の自明パターン
	if (N == 10)
	{
		cout << L_MAX - 1 << endl;
		return 0;
	}

	int used = 0, start = 1;
	for (auto it = prime->begin(); it != prime->end(); ++it)
	{
		if ((*it).usednum & revAA)
		{
			if (used == AA)
			{
				if ((*it).value - start - 1 > LK)
					LK = (*it).value - start - 1;
			}

			start = (*it).value + 1;
			used = 0;
		}
		else
		{
			used |= (*it).usednum;
		}
	}

	//端処理
	if ((used == AA) && (L_MAX - start > LK))
		LK = L_MAX - start;

	cout << LK << endl;

	delete prime;

	return 0;
}
0