- 締切済み
素数
互いに異なる10個の自然数があり、任意の9個を選んで和をとると 素数になる。 こんな、10個の自然数の組で10個の数の和がもっとも小さくなるものを 探すプログラムを作成する。 2週間ほど考えているんですがわかりません。 よろしくお願いします。
- gazettasas
- お礼率50% (1/2)
- C・C++・C#
- 回答数2
- ありがとう数1
- みんなの回答 (2)
- 専門家の回答
みんなの回答
- Werner
- ベストアンサー率53% (395/735)
> S-j = a+b+c+d+e+f+g+h+i+0 = p0 > → j = S-p0 訂正。分かると思いますが S/9-j = a+b+c+d+e+f+g+h+i+0 = p0 → j = S/9-p0 です。
- Werner
- ベストアンサー率53% (395/735)
ちょっと今時間がないので今思いついた考え方だけをそのまま書きます。 (なので、もしかしたら間違っているかもしれません。) > 互いに異なる10個の自然数があり、任意の9個を選んで和をとると素数になる。 この条件より以下の10個の等式が成立する。 (a~jは互いに異なる10個の自然数、p0~p9は素数) a+b+c+d+e+f+g+h+i+0 = p0 a+b+c+d+e+f+g+h+0+j = p1 a+b+c+d+e+f+g+0+i+j = p2 a+b+c+d+e+f+0+h+i+j = p3 a+b+c+d+e+0+g+h+i+j = p4 a+b+c+d+0+f+g+h+i+j = p5 a+b+c+0+e+f+g+h+i+j = p6 a+b+0+d+e+f+g+h+i+j = p7 a+0+c+d+e+f+g+h+i+j = p8 0+b+c+d+e+f+g+h+i+j = p9 以上の等式について両辺の和を取ると、 9*(a+b+c+d+e+f+g+h+i+j) = p0+p1+p2+p3+p4+p5+p6+p7+p8+p9 = S (便宜上、和をSとおく) 9*(a+b+c+d+e+f+g+h+i+j)は9の倍数であるからSも9の倍数である。 ここで、仮に > p0+p1+p2+p3+p4+p5+p6+p7+p8+p9 = S(9の倍数) を満たすSと素数p0~p9の組が見つかったとしよう。 すると、自然数jは以下のようにして求められる。 S-j = a+b+c+d+e+f+g+h+i+0 = p0 → j = S-p0 同様に、他の自然数a~iも求められる。 よって、この問題を解くには、 > p0+p1+p2+p3+p4+p5+p6+p7+p8+p9 = S(9の倍数) を満たす素数の組を見つければよい。 この素数の組を見つけるのは、 素数の集合から和がSになるように部分集合を選ぶという 部分和問題(SUBSET SUM Problem)として解けるのではないかと思います。 (Sを9,18,27と増やしつつ、部分集合が9個の素数になるような解が存在するか確かめていく。)
関連するQ&A
- C言語 素数の和
任意の数から任意の数までの素数の和算出するプログラムが大体できましたがうまく動きません。どこを追加・削除すればいいのでしょうか? 実行例1 数1:10 数2:2 素数の和:17 実行例2: 数1:900 数2:1000 素数の和:13330 参考 2+3+5+7=17 907+911+919+929+937+941+947+953+967+971+977+983+991+997=13330 任意の数から任意の数までの素数の和算出するプログラムがどうしても分かりません。どう作成すればいいのでしょうか? 実行例1 数1:10 数2:2 素数の和:17 実行例2: 数1:900 数2:1000 素数の和:13330 参考 2+3+5+7=17 907+911+919+929+937+941+947+953+967+971+977+983+991+997=13330 #include <stdio.h> #include <math.h> int main(void) { int i, j, k, tmp; int number1, number2, total; printf("数1:"); scanf("%d", &number1); printf("数2:"); scanf("%d", &number2); total = 0; if (number1 > number2) { tmp = number1; number1 = number2; number2 = tmp; } if (number1 == 2) { number1++; total = 2; } if (number1 % 2 == 0) { number1++; } for (i=number1; i<=number2; i+=2) { k=0; for (j=3; j<=sqrt(i); j+=2) { if (i%j==0) { k=1; break; } } if (k==0) { total += i; } } printf("素数の和:%d\n", total); return 0;
- ベストアンサー
- C・C++・C#
- 素数が無限個存在すること(エルデシュによる証明)
素数が無限個存在することの証明について、 素数―wikipedia―によれば、エルデシュによる素数の逆数和の 発散性の証明は、素数が無限個存在することの証明にもなっているらしいです。 (証明において、素数が無限個存在することを用いていないため・・・?) http://ja.wikipedia.org/wiki/%E7%B4%A0%E6%95%B0 その証明は、 背理法による。 n 番目の素数を pn とする。 素数の逆数和が収束すると仮定すると、 任意の ε > 0 に対してある自然数 N が存在して、 1/pN+1 + 1/pN+2 + 1/pN+3 + ... < ε となる。 ★ いま、 ε = 1/2 としよう。任意の自然数 n に対して ・・・・・・・・ と説明されているのですが、 ★マークの部分がよくわかりません。 素数が無限個存在することを使用しているのでは!? もし有限なら、はるかに小さいεがとれないのではないでしょうか? どうかご教授ください。
- ベストアンサー
- 数学・算数
- 1000以下の自然数のうち素数で無いものを全て求め、それらを画面に表示
1000以下の自然数のうち素数で無いものを全て求め、それらを画面に表示しかつそれらの和も画面に表示するC言語のプログラムを作成せよ。 わかりません。お願いいます。
- 締切済み
- C・C++・C#
- 二乗の形は素因数分解すると同じ素数を2個一組になるようにもっているはず!!
他のサイトである質問をしたら、 こういう回答がきました。 36=6^2や64=8^2というある自然数の2乗になる数は、 同じ自然数を2個かけてできているので、 素因数分解すると同じ素数を2個1組になるように持っているはずです。 この文章の、 おんなじ自然数を2個かけてできているので、 素因数分解すると同じ素数を2個1組になるように持っているはず という意味がわかりません。 なぜ持っているはずなのでしょうか? 詳しく教えてください。 一応、他のサイトで質問したものをのせておきます。 http://detail.chiebukuro.yahoo.co.jp/qa/question_detail.php?qid=1125966436
- 締切済み
- 数学・算数
- 1はなぜ素数ではないと決めたのですか?
こんにちは。 素数(そすう)とは、1 とその数自身以外に約数を持たない(つまり1とその数以外のどんな自然数によっても割り切れない)、1 より大きな自然数のことである。 そうですが、なぜ「1 とその数自身以外に約数を持たない」 ものと決めたときに、なぜ1を除外して「1より大きな自然数」と決めたのですか? 1を除外した理由について教えてください。 素数を考える(場合によっては研究)するうえで、1を定義から除外しないとまずくなる決定的な理由あるいは理由を教えてください。 1を素数とすると、存在する数学の定理が成立しなくなるなど、具体的にどんなときなのか教えてください。 お願いいたします。
- ベストアンサー
- 数学・算数
- 自然数の逆数の和について
4つの異なる自然数a.b.c.dの逆数の和をsとします。 sが1より小さいときに、sの最大値はいくつでしょうか? また自然数の個数を任意の自然数にまで拡張した時に 総当たりでなくsの最大値の求める方法はあるのでしょうか?
- 締切済み
- 数学・算数
- 素数の分布について
数Aの問題集をやっていたら参考で載っていたものです。 読んでもわからなかったもので質問させていただきます *-*-*-*-* 素数は無数に存在するが、素数の分布は、自然数が大きくなればなるほど少なくなることが知られている。実際、 101!+2(2の倍数) 101!+3(3の倍数) ・・・・・・・ 101!+101(101の倍数) は連続する100個の合成数で、その間には素数は1個もない。 このようにして任意の戸数の連続する合成数を構成することができる。 *-*-*-*-* なぜ101!が出てくるのでしょうか… そして、なぜその次に数を足しているのでしょうか… たぶんこんなこと入試とか関係ないと思うんですけど(ですよね?;)、本当に全く分からず、なんだかもやもやしていてすごく気持ち悪いものですから… 分かる方いましたら、時間があるときでいいので解説お願いします(^^;)
- ベストアンサー
- 数学・算数
- 2桁の自然数のうち各位の数字の和が奇数になる自然数
問ー 2桁の自然数のうち各位の数字の和が奇数になる自然数は何個? (数学) この問題の意味がはっきりわかりません。 「各位の自然数の和が奇数になる自然数」 ってことは、つまり 和が自然数なのですか? それとも各位が自然数なのですか? (最初の一桁をのぞいて) 自然数は0を含まないので。。。混乱しています。 和は0を含むのでしょうか? 各位は0を含むのでしょうか? (最初の一桁をのぞいて)
- ベストアンサー
- 数学・算数
お礼
回答ありがとうございました。 これを元に一度自分でかみくだきながらプログラム化してみます。 ありがとうございました。