这个问题是我从另一个论坛翻译成英文的，我觉得很有趣，然后写了一个Java解决方案。发现在处理像 10000000 这样的大数字时存在一些堆大小问题。与我自己的相比，我想寻求一些非常聪明的解决方案。
原帖为中文。我根据自己的理解对其进行了一些修改，以使其更清晰。 http://zhidao.baidu.com/question/1637660984282265740.html?sort=6&old=1#here
下面是拼图：
10000 rows of numbers;
1 row: 2,4,6,8...2K(2K<=10000000); (numbers no repeats for this row)
2 row: 3,3,6,6,9,9...3K(3K<=10000000); (starting from this row, each number repeats 2 times and a multiple which has something to do with row number (2XrowNumber-1) to be specificaly)
3 row: 5,5,10,10,15,15...5K(5K<=10000000);
and following 7K,9K,11K,13K....until
10000 row: 19999,19999,39998,39998....19999K,19999K (19999K<=10000000);
这就是下一部分中要使用的所有行。现在我们将计算从第 1 行和第 2 行开始的数字的重复次数：
整数 w1 是第 1 行和第 2 行中数字的重复次数。例如，考虑第 1 行数字 2,4,6 和第 2 行数字 3,3,6,6。那么到目前为止的重复次数将是 3，因为 6 已经在第 1 行并在第 2 行出现了 2 次，而 3 在第 2 行出现了 2 次；
Integer w2 is the repeat times of numbers in row 1 and row 2 and row 3.
Integer w3 is the repeat times of numbers in row 1 and row 2 and row 3 and row 4.
......
Integer w9999 is the repeat times of numbers of row 1,row 2,row 3 .....row 10000.
现在打印出所有整数 w1,w2....w9999;
我想出了一种 Java 解决方案，但是我遇到了堆大小问题，因为 10000000 太大并且内存不够。所以我只用 10000 代替 10000000，用 10 代替 10000。下面是我用 Java 写的。我想应该是对的（如果不对，请指出）：
Set nums = new HashSet();
int max = 10000;
int row = 10;
for (int i=2;i<=max;i+=2){
nums.add(new Integer(i));
}
int nums_size = nums.size();
int w = 0;
for (int i=2;i<=(row);i++){
int tmp_count = 0;
int self_count = 0;
for (int j=(2*i-1);j<=max;j+=(2*i-1)){
nums.add(new Integer(j));
self_count++;
if (nums.size()==nums_size){
tmp_count++;
} else {
nums_size = nums.size();
}
}
w += tmp_count;
w += self_count;
System.out.println("w"+(i-1)+": "+w);
}
我的问题是
- 如何在 Java 中获得更好的解决方案（如果有）？
- 如何在 C 中做到这一点，因为我记得 C 中没有 Set 类。（不推荐导入第 3 方库）？
谢谢。