0

你好我是新程序员，我需要一点点支持我该如何解决这个简单的任务

如果存在整数 M 使得 N = D * M，则正整数 D 是正整数 N 的因数。

例如，6 是 24 的因数，因为 M = 4 满足上述条件 (24 = 6 * 4)。

写一个函数：

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

即，给定一个正整数 N，返回其因子的数量。

例如，给定 N = 24，函数应该返回 8，因为 24 有 8 个因数，即 1、2、3、4、6、8、12、24。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 回答