約数

次の数以下で最も約数が多い数と約数の個数(1とその数含め)を教えて下さい

1,000 約数が多い数840 個数32

(1)10,000

(2)100,000

(3)1,000,000

No.3 ベストアンサー 回答者： tknakamuri 回答日時： 2012/06/24 13:26

反則かもしれませんが、単純にプログラム組んで(Scala)

全数の約数の数を力業で調べました。
なんの工夫もないので 20分位かかりました(^^;

(1) 7560, 9240 で 64個
(2) 83160, 98280 で　128個
(3) 720720, 831600, 942480, 982800, 997920, 240個

No.3 さんと同じ答えなので、多分どちらも正解でしょう。

以下がプログラムです。マイナーな言語ですいません。
＃マイナーといても Twitter の記述言語ですが・・・

import scala.collection.mutable.ArrayBuffer
import scala.util.control.Breaks._

---------- scala プログラム ここから(100万の場合) ----------
object Main {
def isPrime(i: Int): Boolean = {
if (i <= 3) true
else {
val max = (math.sqrt(i) + 0.5).toInt;

for (j <- 2 to max) {
if (i % j == 0)
return false
}

return true
}
}

def main(args: Array[String]): Unit = {
val primes = ArrayBuffer[Int]()

var maxDivisors = 0;
for (i <- 2 to 1000000) {
if (isPrime(i)) {
primes.append(i);
}
}

println("素数の数 = " + primes.length)

for (i <- 2 to 1000000) {

var degrees = List[Int]()
breakable {
for (j <- 0 until primes.length) {
if (primes(j) > i)
break;
var degree = 0
var k = i
while (k % primes(j) == 0) {
degree += 1
k = k / primes(j)
}
if (degree != 0) {
degrees = degrees :+ degree
//println(primes(j) + ", " + degree)
}
}
}

var divisors = 1
for (degree <- degrees) {
divisors *= degree + 1
}
if (divisors >= maxDivisors) {
printf("i = %d, Total = %d\n", i, divisors)
maxDivisors = divisors
}
}
}
}

この回答へのお礼

回答ありがとうございました

お礼日時：2012/06/29 07:03

No.4 回答者： tknakamuri 回答日時： 2012/06/24 23:38

No.3です。

(3)を10秒程度で求められるように改良しました。

import scala.collection.mutable.ArrayBuffer
import scala.util.control.Breaks._

object Main {
def isPrime(i: Int): Boolean = {
if (i <= 3) true
else {
val max = (math.sqrt(i) + 0.5).toInt;

for (j <- 2 to max) {
if (i % j == 0)
return false
}

return true
}
}

def main(args: Array[String]): Unit = {

var maxDivisors = 0;
val primes = 2 to 1001 filter { isPrime(_) }

println("素数の数 = " + primes.length)

for (i <- 2 to 1000000) {
var degrees = List[Int]()
var k = i
var max = (math.sqrt(k) + 0.1).toInt
breakable {
for (j <- 0 until primes.length) {
if (primes(j) > max) {
if (k > 1) {
degrees = degrees :+ 1
}
break;
}
var degree = 0
while (k % primes(j) == 0) {
degree += 1
k = k / primes(j)
}
if (degree != 0) {
degrees = degrees :+ degree
}
}
}

var divisors = 1
for (degree <- degrees) {
divisors *= degree + 1
}
if (divisors >= maxDivisors) {
printf("i = %d, Total = %d\n", i, divisors)
maxDivisors = divisors
}
}
}
}

この回答へのお礼

回答ありがとうございました。

お礼日時：2012/06/29 07:01

No.2 回答者： momordica 回答日時： 2012/06/23 22:25

> 1,000 約数が多い数840 個数32

「1000以下の自然数で最も約数が多い数は840で、その約数の個数は32個」
という意味ですよね。

1万、10万、100万以下の場合、それぞれ同じ最大個数になる数が複数あるようですが、

(1)
　7560 = 2^3 * 3^3 * 5 * 7
　9240 = 2^3 * 3 * 5 * 7 * 11
　　約数の個数は64個

(2)
　83160 = 2^3 * 3^3 * 5 * 7 * 11
　98280 = 2^3 * 3^3 * 5 * 7 * 13
　　約数の個数は128個

(3)
　720720 = 2^4 * 3^2 * 5 * 7 * 11 * 13
　831600 = 2^4 * 3^3 * 5^2 * 7 * 11
　942480 = 2^4 * 3^2 * 5 * 7 * 11 * 17
　982800 = 2^4 * 3^3 * 5^2 * 7 * 13
　997920 = 2^5 * 3^4 * 5 * 7 * 11
　　約数の個数は240個

でいいかと思います。　違ってたらすみません。

この回答へのお礼

回答ありがとうございました

お礼日時：2012/06/29 07:04

No.1 回答者： spring135 回答日時： 2012/06/23 13:40

＞1,000 約数が多い数840 個数32

意味不明です。国語になっていません。もちろん数学にも。

この回答へのお礼

回答ありがとうございました

お礼日時：2012/06/29 07:05