220507

Ruby


和と差の積を用いた素因数分解

nを素因数分解しようとすれば、√n 以下の素数を順番に割る方法もあるが、

受験数学では、和と差の積を用いた方法を使う方が速い場合が多い。

ここでは、後者の方法を実装してみた。

（ただし、偶数の場合は、2で割り続ければ、奇数になるので、

奇数の場合の素因数分解について考える。）

def is_square(n)
  n == Math.sqrt(n).to_i ** 2
end

def A(n)
  a = Math.sqrt(n).ceil
  while !is_square(a * a - n)
    a += 1 
  end
  b = Math.sqrt(a * a - n).to_i
  c, d = a - b, a + b
  return [A(c), A(d)] if c > 1
  [d]
end

n = 200
3.step(2 * n - 1, 2){|i| p [i, A(i)]}

出力結果

[3, [3]]

[5, [5]]

[7, [7]]

[9, [[3], [3]]]

[11, [11]]

[13, [13]]

[15, [[3], [5]]]

[17, [17]]

[19, [19]]

[21, [[3], [7]]]

[23, [23]]

[25, [[5], [5]]]

[27, [[3], [[3], [3]]]]

[29, [29]]

[31, [31]]

[33, [[3], [11]]]

[35, [[5], [7]]]

[37, [37]]

[39, [[3], [13]]]

[41, [41]]

[43, [43]]

[45, [[5], [[3], [3]]]]

[47, [47]]

[49, [[7], [7]]]

[51, [[3], [17]]]

[53, [53]]

[55, [[5], [11]]]

[57, [[3], [19]]]

[59, [59]]

[61, [61]]

[63, [[7], [[3], [3]]]]

[65, [[5], [13]]]

[67, [67]]

[69, [[3], [23]]]

[71, [71]]

[73, [73]]

[75, [[5], [[3], [5]]]]

[77, [[7], [11]]]

[79, [79]]

[81, [[[3], [3]], [[3], [3]]]]

[83, [83]]

[85, [[5], [17]]]

[87, [[3], [29]]]

[89, [89]]

[91, [[7], [13]]]

[93, [[3], [31]]]

[95, [[5], [19]]]

[97, [97]]

[99, [[[3], [3]], [11]]]

[101, [101]]

[103, [103]]

[105, [[7], [[3], [5]]]]

[107, [107]]

[109, [109]]

[111, [[3], [37]]]

[113, [113]]

[115, [[5], [23]]]

[117, [[[3], [3]], [13]]]

[119, [[7], [17]]]

[121, [[11], [11]]]

[123, [[3], [41]]]

[125, [[5], [[5], [5]]]]

[127, [127]]

[129, [[3], [43]]]

[131, [131]]

[133, [[7], [19]]]

[135, [[[3], [3]], [[3], [5]]]]

[137, [137]]

[139, [139]]

[141, [[3], [47]]]

[143, [[11], [13]]]

[145, [[5], [29]]]

[147, [[7], [[3], [7]]]]

[149, [149]]

[151, [151]]

[153, [[[3], [3]], [17]]]

[155, [[5], [31]]]

[157, [157]]

[159, [[3], [53]]]

[161, [[7], [23]]]

[163, [163]]

[165, [[11], [[3], [5]]]]

[167, [167]]

[169, [[13], [13]]]

[171, [[[3], [3]], [19]]]

[173, [173]]

[175, [[7], [[5], [5]]]]

[177, [[3], [59]]]

[179, [179]]

[181, [181]]

[183, [[3], [61]]]

[185, [[5], [37]]]

[187, [[11], [17]]]

[189, [[[3], [3]], [[3], [7]]]]

[191, [191]]

[193, [193]]

[195, [[13], [[3], [5]]]]

[197, [197]]

[199, [199]]

[201, [[3], [67]]]

[203, [[7], [29]]]

[205, [[5], [41]]]

[207, [[[3], [3]], [23]]]

[209, [[11], [19]]]

[211, [211]]

[213, [[3], [71]]]

[215, [[5], [43]]]

[217, [[7], [31]]]

[219, [[3], [73]]]

[221, [[13], [17]]]

[223, [223]]

[225, [[[3], [5]], [[3], [5]]]]

[227, [227]]

[229, [229]]

[231, [[11], [[3], [7]]]]

[233, [233]]

[235, [[5], [47]]]

[237, [[3], [79]]]

[239, [239]]

[241, [241]]

[243, [[[3], [3]], [[3], [[3], [3]]]]]

[245, [[7], [[5], [7]]]]

[247, [[13], [19]]]

[249, [[3], [83]]]

[251, [251]]

[253, [[11], [23]]]

[255, [[[3], [5]], [17]]]

[257, [257]]

[259, [[7], [37]]]

[261, [[[3], [3]], [29]]]

[263, [263]]

[265, [[5], [53]]]

[267, [[3], [89]]]

[269, [269]]

[271, [271]]

[273, [[13], [[3], [7]]]]

[275, [[11], [[5], [5]]]]

[277, [277]]

[279, [[[3], [3]], [31]]]

[281, [281]]

[283, [283]]

[285, [[[3], [5]], [19]]]

[287, [[7], [41]]]

[289, [[17], [17]]]

[291, [[3], [97]]]

[293, [293]]

[295, [[5], [59]]]

[297, [[11], [[3], [[3], [3]]]]]

[299, [[13], [23]]]

[301, [[7], [43]]]

[303, [[3], [101]]]

[305, [[5], [61]]]

[307, [307]]

[309, [[3], [103]]]

[311, [311]]

[313, [313]]

[315, [[[3], [5]], [[3], [7]]]]

[317, [317]]

[319, [[11], [29]]]

[321, [[3], [107]]]

[323, [[17], [19]]]

[325, [[13], [[5], [5]]]]

[327, [[3], [109]]]

[329, [[7], [47]]]

[331, [331]]

[333, [[[3], [3]], [37]]]

[335, [[5], [67]]]

[337, [337]]

[339, [[3], [113]]]

[341, [[11], [31]]]

[343, [[7], [[7], [7]]]]

[345, [[[3], [5]], [23]]]

[347, [347]]

[349, [349]]

[351, [[13], [[3], [[3], [3]]]]]

[353, [353]]

[355, [[5], [71]]]

[357, [[17], [[3], [7]]]]

[359, [359]]

[361, [[19], [19]]]

[363, [[11], [[3], [11]]]]

[365, [[5], [73]]]

[367, [367]]

[369, [[[3], [3]], [41]]]

[371, [[7], [53]]]

[373, [373]]

[375, [[[3], [5]], [[5], [5]]]]

[377, [[13], [29]]]

[379, [379]]

[381, [[3], [127]]]

[383, [383]]

[385, [[11], [[5], [7]]]]

[387, [[[3], [3]], [43]]]

[389, [389]]

[391, [[17], [23]]]

[393, [[3], [131]]]

[395, [[5], [79]]]

[397, [397]]

[399, [[19], [[3], [7]]]]