AIZU ONLINE JUDGE (AOJ) - 0044 について

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
アバター
vow256
記事: 13
登録日時: 3ヶ月前
連絡を取る:

AIZU ONLINE JUDGE (AOJ) - 0044 について

#1

投稿記事 by vow256 » 3ヶ月前

AIZU ONLINE JUDGE (AOJ) の 0044 に関して質問です。
複数のデータセットが与えられます。
各データセットに n (3 ≤ n ≤ 50,000) が1行に与えられます。
データセットの数は 50 を超えません。
各データセットに対して、n より小さい素数のうち最大のものと、n より大きい素数のうち最小のものを1つのスペースで区切って1行に出力して下さい。
という問題に対し、以下のようなコードを作成しました。

コード:

#include <iostream>
using namespace std;

int main() {
	int n;
	while (cin >> n) {
		int max_num = 0;
		int new_num = 0;
		int sn = n;
		int bn = n;
		while (1) {
			sn--;
			bn++;
			if (max_num == 0) {
				if (sn <= 3) {
					if (sn == 2 || sn == 3) max_num = sn;
					continue;
				}
				else {
					if (sn % 2 == 0 || sn % 3 == 0) continue;
					if (sn % 6 != 1 && sn % 6 != 5) continue;
					bool check = true;
					for (int j = 5; j * j <= sn; j += 6) {
						if (sn % j == 0) check = false;
						if (sn % (j + 2) == 0) check = false;
						if (check == false) break;
					}
					if (check == true) max_num = sn;
				}
			}
			if (new_num == 0) {
				if (bn <= 3) {
					if (bn == 2 || bn == 3) new_num = bn;
					continue;
				}
				else {
					if (bn % 2 == 0 || bn % 3 == 0) continue;
					if (bn % 6 != 1 && bn % 6 != 5) continue;
					bool check = true;
					for (int j = 5; j * j <= bn; j += 6) {
						if (bn % j == 0) check = false;
						if (bn % (j + 2) == 0) check = false;
						if (check == false) break;
					}
					if (check == true) new_num = bn;
				}
			}
			if (max_num != 0 && new_num != 0) break;
		}
		cout << max_num << " " << new_num << endl;
	}
	return 0;
}
素数は 2 と 3 を除いて全て 6n ± 1 (n は自然数) で表されるため、その性質を利用して作成したコードとなっています。
しかし、自動審判で誤答と判定されたため適当な数字を入力してみると 7 の場合に出力が 3 と 11 となっていることに気づきました。
自分のケアレスミスか何かだとは思うのですが、自分では間違っている箇所に気づくことが出来なかったので指摘していただきたいです。

box
記事: 1701
登録日時: 7年前

Re: AIZU ONLINE JUDGE (AOJ) - 0044 について

#2

投稿記事 by box » 3ヶ月前

何でもかんでもmain()に押し込むのではなく、
例えば今回の場合、「引数で与えた数が素数かどうかを判定する」という機能を
関数にしてみると、何か見えてくるかもしれません。
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。

アバター
vow256
記事: 13
登録日時: 3ヶ月前
連絡を取る:

Re: AIZU ONLINE JUDGE (AOJ) - 0044 について

#3

投稿記事 by vow256 » 3ヶ月前

変更後のコードです。

コード:

#include <iostream>
using namespace std;

bool prime(int n) {
	switch (n) {
	case 1: return false;
	case 2: return true;
	case 3: return true;
	}
	if (n % 2 == 0 || n % 3 == 0) return false;
	if (n % 6 != 1 && n % 6 != 5) return false;
	for (int i = 5; i * i <= n; i += 6) {
		if (n % i == 0) return false;
		if (n % (i + 2) == 0) return false;
	}
	return true;
}

int main() {
	int n;
	while (cin >> n) {
		int sn = 0;
		int bn = 0;
		if (n % 2 == 0) {
			for (int i = 1;; i += 2) {
				if (sn == 0 && prime(n - i) == true) sn = n - i;
				if (bn == 0 && prime(n + i) == true) bn = n + i;
				if (sn != 0 && bn != 0) break;
			}
		}
		else {
			for (int i = 2;; i += 2) {
				if (sn == 0 && prime(n - i) == true) sn = n - i;
				if (bn == 0 && prime(n + i) == true) bn = n + i;
				if (sn != 0 && bn != 0) break;
			}
		}
		cout << sn << " " << bn << endl;

	}
	return 0;
}
正しい値を示すようにはなったのですが、次は時間制限に引っかかってしまったようです。
ループが多いのでそうなってしまうのは分かるのですがどこを変更したほうが良いのでしょうか。
それとも、そもそもこの方法の効率が悪いのでしょうか。

かずま

Re: AIZU ONLINE JUDGE (AOJ) - 0044 について

#4

投稿記事 by かずま » 3ヶ月前

vow256 さんが書きました:
3ヶ月前
正しい値を示すようにはなったのですが、
n = 3 のときは正しい値を示さないようです。
vow256 さんが書きました:
3ヶ月前
それとも、そもそもこの方法の効率が悪いのでしょうか。
割り算が多いから効率が悪いのではないでしょうか?

エラトステネスの篩を使うと、足し算だけで素数判定表が作れます。

コード:

#include <iostream>

const int PRIME = 50021, SQRT_PRIME = 223;
bool not_prime[PRIME + 1];

int main()
{
	for (int i = 2; i <= SQRT_PRIME; i++)
		if (!not_prime[i])
			for (int j = i + i; j <= PRIME; j += i)
				not_prime[j] = true;
	int n, a, b;
	while (std::cin >> n) {
		a = b = n;
		while (not_prime[--a]) ;
		while (not_prime[++b]) ;
		std::cout << a << ' ' << b << '\n';
	}
}

アバター
vow256
記事: 13
登録日時: 3ヶ月前
連絡を取る:

Re: AIZU ONLINE JUDGE (AOJ) - 0044 について

#5

投稿記事 by vow256 » 3ヶ月前

エラトステネスの篩は思いつきませんでした。
もう少し熟考しないとダメですね。
ご丁寧にありがとうございました。

返信

“C言語何でも質問掲示板” へ戻る