

x,y,nを正の整数として、1/x + 1/y =
1/nかつx<=yを満たす解の個数が1000を超える最小のnを求めるプログラムを作りたいのですが、以下のプログラムをpaizaで書いてもtime.outと出てしまいます。どうすれば時間がかからずに答えを求めることができますか？

ヒントとして「a,b(a<=b)を正の整数として、x=n+a,y=n+bとおくと，条件式はn²=abとなる。よって、a,bは、n²の約数に限定される。」と書かれています。

[code]

    public class Main {
        public static void main(String[] args) throws Exception {
            int n=1;    
            while(true){
                int sum = 0;
                for(int x = n + 1; x <= n * 2; x++) {
                    int y = x * n / (x - n);
                    if(Math.pow(n,2) == x*y && x <= y){
                        if(x * n % (x - n) == 0) { 
                            sum = sum + 1;
                            if(sum > 1000){
                                break; 
                            }
                        }
                    }
                    n++;
                }
                System.out.println(n);
            }
        }
    }
    
[/code]


CC BY-SA 4.0
2023-01-24T14:38:19.050
93549
2023-01-25T12:56:07.593
2023-01-25T03:49:24.773
3060
55336
question
java
条件を満たす解を求めるプログラムの実行時間を改善したい


実行時間の改善以前に、このプログラムは題意を満たしていません。

  1. このプログラムは終了しません。 ※ `while(true)`から抜け出すコードがありません。
  2. n=1のときx=2、y=2の解が存在しますがsumがカウントされません。
  3. 約数xと約数yのペアをカウントしているようです。xとyが等しいときを考慮すると約数の個数はsum*2-1だと思います。

まずn=1のときの動作を確認した方がよいです。


CC BY-SA 4.0
2023-01-25T06:48:47.613
93558
2023-01-25T12:56:07.593
2023-01-25T12:56:07.593
35558
35558
93549
answer