No.1
- 回答日時:
まず, ちょっと考えれば
・2以上 √N 以下のどの整数でも割り切れないなら N は素数
であることがわかります (N = pq とおくと p と q の一方は √N 以下). また,
・N を割り切る (2以上の) 最小の整数が素数
であることも簡単にわかります (素数でないと仮定して背理法が簡単?).
だから「no や i が非素数」ということはありえません.
No.2
- 回答日時:
Nが素数なら、2<=i<=√Nの範囲で、whileループ条件であるno%i==0にあてはまるiは存在しないので、no/=iは実行されることがなく、no=Nのまま終了します。
whileループでは、一度no%i==0の条件に当てはまったら、そのiでnoが割り切れなくなるまで繰り返します。
それを、i*i<noの条件を満たす限り、iを大きくしながら繰り返します。
noを割り切れるiがなくなったら、終了。
終了した時点で、noを割り切れるi(素数)がないんだから、noは素数ですよね。
iは2から1ずつ大きくしているから、iが非素数であることはありますが、forループでiがそんな値になったときには、whileループ条件のno%i==0には当てはまらないようになっています。
No.3
- 回答日時:
a<b<cで、c=a*bだとして、i=cになった時点で、noは素因数にaもbも含まない状態になっているので、aとbの積であるcも当然noの素因数には含まれません。
なので、no%i==0の条件を満たすことはなく、no/=iの処理も行われません。
No.4
- 回答日時:
リンク先の質問でも答えたのですが
このアルゴリズムは, iもnoも非素数になる場合があります
Nが素数のべき乗になっている場合です
例えば
N=81 (3の4乗)の場合です
iとnoの値を追いかけてみます
まず
int i,no=81; のように変数に値をセットして, for文の繰り返しを実行します
i=2のとき, 2*2 <= 81なので, forのカッコ内を処理する
81 % 2 != 0なので, whileのカッコ内の処理をしない
i=3のとき, 3*3 <= no (=81)なので, forのカッコ内を処理する
81 % 3 == 0なので, whileのカッコ内の処理(no = 81/3 = 27)をする
27 % 3 == 0なので, 同様にno = 27/3 = 9をする
9 % 3 == 0なので, 同様にno = 9/3 = 3をする
3 % 3 == 0なので, 同様にno = 3/3 = 1をする
1 % 3 != 0なので, whileのカッコ内の処理をしない
i=4のとき, 4*4 > no (=1)なので, forのカッコ内を処理しない
となって, 繰り返しが終了します
このとき
i=4, no=1 ですが, これらは81の最大の素因数ではありません
参考URL:http://detail.chiebukuro.yahoo.co.jp/qa/question …
No.5ベストアンサー
- 回答日時:
ANo.4で参考に挙げた知恵袋の質問が消えそうなので
そちらで紹介した代替案を転載します
----
こんな方法ではどうでしょう?
int no = N;
int i, p = 1;
// iは素因数候補, pは各段階での最大素因数
for(i=2;i*i <= no;i++){
if(no % i == 0){
p = i; // より大きい素因数が見つかったので, 最大素因数を更新する
while(no % i == 0) no /= i; // noを素因数候補iで割れるだけ割る
}
}
// no = 3*7のように最大素因数が√noより大きい場合は最後のnoが最大素因数
if(no > p) p = no;
最後にはpにNの最大の素因数が入っていることになります
しくみは以下のとおり
noが素数か1になるまで素因数候補i で小さいものから順に割り続けます
すると素因数候補i が合成数の場合には絶対にnoを割り切れなくなります
ですので
noの最大の素因数は, 素数になったときのnoか最後にnoを割り切った数のどちらかです
あとは, noと最後にnoを割り切った数pを比較して大きい方を選べば
最大の素因数が得られることになります
----
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- C言語・C++・C# C言語 プログラミング 4 2022/05/22 11:53
- 数学 nは正の整数であり、偶数。 n(n+1)(n+2)(n+3)は素因数が3つ。 nを求めよ。 という問 8 2022/09/26 18:15
- 数学 これまでに愚かな回答者を何人も見てきました。 それでも私は問うてみたい。 京都大学の入試問題に 「 6 2023/05/01 14:06
- Excel(エクセル) vba シート名の一覧を2列に分けるには 5 2023/04/24 08:56
- Visual Basic(VBA) VBAで、1つのエクセルで、2つのシートからもう1つのシートに条件のある転記コードを教えてください。 1 2023/03/16 18:07
- 数学 中一数学の【最大公約数と最小公倍数】の問題です。 1問だけでも教えていただけると嬉しいです。 (1) 4 2022/08/01 10:19
- Visual Basic(VBA) VBAで大量データの処理 3 2022/11/15 21:53
- 数学 【 数A 自然数の積と素因数の個数 】 2 2023/03/02 23:58
- 数学 どうか教えてください。 4 2022/07/02 20:18
- Google Maps エクセルについて 2 2022/11/27 11:00
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
小学5年算数。階乗の関数
-
数学 2時間数に関わる問題につ...
-
MOS365 Excel Expert / Excel R...
-
数学の表記の表し方で最大値と...
-
x(x-1)(x-2)(x-3)の最大値と最...
-
極大値・極小値 を英語で
-
二次関数の最小値・最大値の問題
-
Ankerのケーブルについて Anker...
-
2次関数y=f(x)=−x^2+2ax+1(−1...
-
Nを5進法であらわすと4桁で表さ...
-
80Ck (Cはコンビネーション)が...
-
二変数関数の最大値と最小値に...
-
レーダーチャートの軸
-
マルチディスプレイ【2台】に...
-
東大理系数学第4問の(3)について
-
数的推理 整数 問題 4個の自然...
-
max,minの意味
-
次の二次関数の最大値、最小値...
-
はめあいの『最大すきま』と『...
-
停留点
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
極大値・極小値 を英語で
-
小学5年算数。階乗の関数
-
aを正の定数とし、f(x)=x²+2(a-...
-
MOS365 Excel Expert / Excel R...
-
なぜ、最小値がないのかが分か...
-
①とても初歩的なことなのですが...
-
数学I y=-(x^2-4x+1)^2+2x^2-8x...
-
(2)の問題を解くときに、最初...
-
マルチディスプレイ【2台】に...
-
3σと最大値,最小値
-
上界と上限と最大値の違い
-
数値データの規格化
-
基本情報処理 平成27年春期 ...
-
数学 2時間数に関わる問題につ...
-
max,minの意味
-
はめあいの『最大すきま』と『...
-
y=-|x-2|+3のグラフで 問題 ...
-
最大値=∞ というように無限を解...
-
正と負の数値が混在する中で、...
-
絶対最大値と絶対最小値って何...
おすすめ情報