0

こんにちは、私は新しいプログラマーです。この単純なタスクを解決するにはどうすればよいか、少しサポートが必要です

N = D * M となる整数 M が存在する場合、正の整数 D は正の整数 N の約数です。

たとえば、M = 4 は上記の条件 (24 = 6 * 4) を満たすため、6 は 24 の係数です。

関数を書く:

class Solution { public int count_factors(int N); }

これは、正の整数 N を指定すると、その因数の数を返します。

たとえば、N = 24 の場合、24 には 1、2、3、4、6、8、12、24 という 8 つの因数があるため、関数は 8 を返す必要があります。24 には他の因数はありません。

と仮定する：

N is an integer within the range [1..2,147,483,647]

複雑：

expected worst-case time complexity is O(sqrt(N))
expected worst-case space complexity is O(1)
4

3 に答える 3

2

最悪の場合の時間計算量はO(sqrt(N))です。最悪の場合のスペースの複雑さはO(1)です。

public class Solution
{
    public static void main(String[] args)
    {
        final Solution solution = new Solution();
        for (int i = 1; i < 25; i++)
        {
            System.out.println(i + " has " + solution.count_factors(i) + " factor(s)");
        }
    }

    public int count_factors(int N)
    {
        int result = 0;
        final int sqrtN = (int) Math.sqrt(N);
        for (int i = 1; i <= sqrtN; i++)
        {
            if (N % i == 0)
            {
                // We found 2 factors: i and N/i.
                result += 2;
            }
        }
        if (sqrtN * sqrtN == N)
        {
            // We counted sqrtN twice.
            result--;
        }
        return result;
    }
}

出力：

1 has 1 factor(s)
2 has 2 factor(s)
3 has 2 factor(s)
4 has 3 factor(s)
5 has 2 factor(s)
6 has 4 factor(s)
7 has 2 factor(s)
8 has 4 factor(s)
9 has 3 factor(s)
10 has 4 factor(s)
11 has 2 factor(s)
12 has 6 factor(s)
13 has 2 factor(s)
14 has 4 factor(s)
15 has 4 factor(s)
16 has 5 factor(s)
17 has 2 factor(s)
18 has 6 factor(s)
19 has 2 factor(s)
20 has 6 factor(s)
21 has 4 factor(s)
22 has 4 factor(s)
23 has 2 factor(s)
24 has 8 factor(s)
于 2013-03-18T18:38:13.090 に答える
0 
 public int count_factors(int N)
 {
  int count = 2;
  for(int i=2; i<=N/2; i++)
  {
    if(N%i==0) count++;
  }
  return count;
 }

これでうまくいくはずです。

于 2013-03-18T18:32:31.173 に答える
0 
public int count_factors(int N) {
    int numFactors = 2; //1 and N are factors
    double sqrtN = Math.sqrt(N);
    if((sqrtN == Math.ceil(sqrtN))) //If sqrt(N) has no fractional part don't include N itself
        numFactors=1;
    for(int i=2; i <= sqrtN; i++) {
        if(N%i == 0)
            numFactors +=2; // i and N/i are factors
    }
    return numFactors;
}
于 2013-03-18T19:02:23.843 に答える